Overall the present inventive aspects provide an alternative to the network routing of the prior art fixed networks.

BACKGROUND ART MOBILE AD HOC NETWORKS As an alternative to cellular networks, infrastructureless or mobile ad hoc networks (MANET) are designed for use in areas where there might not be permanent signal coverage. These are networks in which the radio transmission range of a node is limited and the topology of the network is dynamic, so that multihop communication is necessary for nodes to communicate with each other.

The reliance on wireless multihop communication to maintain connectivity among nodes places added complexity on the design and operation of these networks. It is foreseeable that nodes will have different transceivers and antennas, and these differences must also be considered when setting up an infrastructureless network.

Proponents of ubiquitous computing contend that computing devices will be embedded in our living and working spaces. Rooms, home appliances, corridors, vehicles, and public areas might one day each contain hundreds or thousands of computers, which can be interconnected most effectively by means of a wireless network. Although most of the embedded devices would be fixed, it is expected that devices embedded in movable furniture, equipment, or vehicles will be considered mobile or nomadic. Furthermore, users will certainly move from area to area, expecting to have instantaneous connectivity to local embedded devices.

While ubiquitous computing seeks to provide wireless access to information for the peripatetic user who wanders from room to room, micronetworks embed small devices, such as microelectomechanical systems, in hostile or inaccessible environments. As the nature of the environment often makes a wired interconnection impractical or too costly, a wireless network is typically the preferred regime for interconnecting the embedded devices. Such devices might be manufactured into building materials that are used to construct an edifice or vehicle, endowed with special- ability to monitor strain gauges or accelerometers and pass the information on to a central controller. Given that the embedding matrix itself (e. g., the frame of an aircraft) might be mobile, the micronetwork is also mobile from the point of view of a global backbone wired network.

Management and control of infrastructureless networks is an important area that will probably draw upon different solutions than are found in either cellular or wired networks. The need to report on a dynamically changing topology that suggests a more-autonomous style of network management than one finds in today's polling-based systems. Also, the sheer number of nodes that one might find in a ubiquitous computing network or a micronetwork underscores the need for a level of scalability not commonly present in most approaches to network management.

APPLICATION ENVIRONMENTS By way of illustration, MANETs can be present in a number of applications. Military Communication Networks-With reference to Figure 1, in military, soldiers equipped with multimode mobile communicators can now communicate in an ad hoc manner without the need for fixed wireless base stations. In addition, small vehicular devices equipped with audio sensors and cameras can be deployed at targeted regions to collect important location and environmental information that will be communicated back to a processing node via ad hoc mobile communications. Ship-to-ship ad hoc mobile communication is also desirable since it provides alternate communication paths without reliance on ground or space based communication infrastructures.

As shown in the Figure 1, the mobile node by moving between two clusters of ad hoc networks becomes a router node and links the two clusters.

Home Networks-An ad hoc network comprised of various computing devices and other entertainment devices at home could be formed, and it can be linked to the Internet through a home gateway. In such environments, the Bluetooth technology is quite suitable for realising the wireless connectivity.

Networked Toys-Electronic toys are being equipped with computing and communication capabilities. In future, such toys, when brought together will be able to form a community and communicate with each other. Mobile ad hoc networks can play a key role in such toys communication.

Wireless Sensor Network-Large-scale networks of wireless sensors are becoming an active topic of research. Advances in hardware technology and engineering design have lead to dramatic reductions in size, power consumption, and cost for Micro Electro Mechanical Systems (MEMS)-based sensors. This has enabled very compact, autonomous and mobile nodes, and each containing one or more sensors, computation and communication capabilities, and a power supply.

Meeting and Conference Sites-People today attend meetings and conferences with their laptops, or palmtops, or notebooks. It is therefore attractive to have instant network information, in addition to file and information sharing without the presence of fixed base stations and system administrators.

Presenters can multicast slides and audio to intended recipients. Attendees can ask questions and interact on a commonly shared whiteboard.

Emergency/Rescue Environments-Ad hoc mobile communication is particularly useful in relaying information via data, video, and/or voice from one rescue team member to another over a small handheld or wearable wireless device.

Other Areas-Wearable computing, Emergency services, Law enforcement, and Logistics industry.

AD HOC NETWORK TECHNIQUES In Ad hoc networks, mobile terminals with wireless connectivity communicate with each other without any fixed topology. When there is no direct

wireless link between two nodes, the intermediate nodes could be used to forward the packets. Existing proposals are based on network layer (layer 3) routing. In the case of Internet protocols, the intermediate terminals act as routers, forwarding the IP packets.

In the Internet, when a packet needs to be forwarded, the router needs to know the address of the next hop (node) to which the packet should traverse. The next hop address can either be pre-determined and maintained in a table (routing table) or can be explicitly given in the packet header. In the former case, a routing protocol is used to determine the next hop address based on the packet destination address and one or more optimality criteria. Based on the destination address, the table is looked up to determine the next hop address. Routing information is exchanged between nodes periodically and the routing table is updated accordingly. It is also called a table driven approach. In the latter case, every packet to be forwarded contains the address of every hop it has to traverse and hence there is no need to maintain a routing table at every node. It is also called source routing. Variations of these routing protocols are considered for the MANET because of the changing topology, limited radio resource, and due to the fact that every terminal is a potential router. There are several protocols proposed for routing IP packets in a MANET. They are mostly on-demand routing protocols. For example, Ad hoc On-Demand Distance Vector Routing (AODV) and Dynamic Source Routing (DSR) are two of the routing protocols which have been proposed in the IETF MANET working group. With on-demand routing, when a route is needed, the routing protocol attempts to find a route for the current data communication session. On-demand routing does not require each node to continuously evaluate and maintain all the routes to every other node in the network, as required with table-driven routing, thus avoiding the need to frequently exchange state information, reducing the amount of update traffic, and conserving limited resources.

AODV is based on a distance vector routing mechanism and uses a route table to find the next hop in the route. AODV assumes symmetric links in the ad hoc network and hence cannot work properly in ad hoc networks having asymmetric links. DSR is based on a source routing mechanism and can work in

ad hoc network having asymmetric links. However, DSR requires that the entire route map be carried with each data packet in order for the packet to reach its destination. Although DSR does not involve the route table lookup required by AODV, it nevertheless involves heavy routing overhead in each data packet.

Other routing protocols include Associativity-Based long-lived Routing (ABR) and Cluster Based Routing Protocol (CBRP).

A mobile ad hoc network comprising a number of user terminals capable of performing data link (DL) layer bridging is shown in Figures 2 and 3. The bridge listens to all DL frames and forwards them, if necessary, using a bridging algorithm.

ALGORITHMS Bridging Algorithms (e. g., IEEE 802.1d) have been well studied in the case of wired LANs, especially Ethernet and Token Ring (IEEE 802.3,802.5).

These bridges use the following algorithms: Spanning tree Source routing The bridges may also use other algorithms optimised for wireless networks. Discovering the topology and route are specific to the algorithm used.

Different Bridging Scenarios In wired LANs, bridges are used to extend the coverage area in a transparent manner. However, in wireless LANs, the reachability within a WLAN is also important due to specific problems like hidden terminals. As a result, the different types of bridges in a wireless LAN can be classified as follows : Intra-LAN bridging When there is only a single radio cell in a LAN as shown in Figure 2, the hidden terminal problem prevents some terminals from direct communication. In this case, some intermediate terminal (node) can bridge these terminals.

Inter-LAN bridging-Fixed Bridges In this case, there are multiple LANs using different overlapping radio cells, as shown in Figure 3. Stationary bridges can be used to interconnect two nodes on adjacent LANs. In this case, the traditional wired LAN bridging algorithms

such as spanning tree/source routing algorithm can be used with minor modifications.

Inter-LAN bridging-Mobile Bridges In this case too, there are multiple LANs using different overlapping radio cells as shown in Figure 3. Mobile nodes acting as bridges can be used to interconnect two nodes on different LANs. In this case, the traditional wired LAN bridging techniques such as spanning tree algorithm cannot be used due to bridge mobility.

PROBLEMS Some of the problems and challenges associated with ad hoc networks are the following : Path (route) discovery-the mobility of terminals cause the path to change dynamically.

Packet Forwarding-in order to maintain the connectivity in an ad hoc network, a mobile terminal has to perform the additional functionality of forwarding the packets between other terminals.

QoS-the characteristics of the wireless medium changes randomly and hence the QoS guarantees in such environments is a challenge Handoff-in order to maintain the continuity of communication, handoff may be necessary in a mobile ad hoc network.

Autoconfiguration-since there is no central server in a mobile ad hoc network, the existing autoconfiguration techniques for address assignment and service discovery for fixed networks cannot be directly applied in a mobile ad hoc network.

It is an object of the present invention to seek to address these and other problems associated with prior art ad hoc networks.

There is also a need to provide an architecture for relatively simple, fast and efficient connectivity among the terminals in a mobile ad hoc network.

There is further, a need to provide a relatively simple, distributed and efficient algorithm for bridging in such networks.

There is still further, a need to provide a relatively simple, distributed and efficient solution for auto-configuration in such mobile ad hoc networks.

SUMMARY OF INVENTION In this regard, the present invention in one aspect provides, in a mobile ad hoc network having a plurality of mobile and/or fixed user terminals, a method of bridging between a first and a second terminal, the method including the step of: Using a third terminal to act as a data link layer (layer 2) bridge between the first and the second terminal.

Preferably, the act of bridging of the third terminal includes broadcasting control and current network information.

Preferably, each terminal is adapted to bridge communication based on stored network information.

The present inventive aspect has come about by enabling the intermediate nodes to act as a data link layer (layer 2) bridges, and which is expected to be relatively faster and efficient compared to the network layer routing, due to the following reasons: No network layer processing and hence better performance compared to routers Relatively simpler forwarding tables at the data link layer, compared to network layer Independent of network layer protocols-any network layer protocol including IP can be used Low power consumption due to simpler protocol processing Bridges are considered to be plug and play devices compared to routers.

This invention addresses bridging within a wireless LAN and between wireless LANs. It also addresses other issues in mobile ad hoc networks such as auto- configuration and handoff.

The present invention provides, in a second aspect, in a system for mobile ad hoc (or infrastructure-less) communication, the system including a plurality of mobile and/or fixed user terminals adapted to serve as data link layer bridges, to link user terminals which are otherwise unable to communicate directly, a method of providing path discovery including the step of: broadcasting control information across a radio cell.

In this inventive aspect, passive route (path) discovery is proposed. As opposed to the on-demand route discovery proposed in the ad hoc routing proposals of prior art MANETs, the availability of a mobile terminal will be announced by the terminal itself and this information will be broadcast across the entire network through intermediate bridges. This saves the number of path discoveries needed to determine the presence or availability of a terminal.

The path discovery is done by exchanging control messages. It is realised using the following types of control messages: Attachment Detachment Query Response The present invention provides, in a third aspect, a method of auto- configuration of addresses and service discovery in a system for mobile ad hoc communication, including the steps of: (v) The user terminal broadcasting its details after attachment; (w) One of the user terminals broadcasting the assigned address (address allocator) ; (x) Other terminals updating their database; (y) The user terminal broadcasting the detachment from the radio cell ; (z) Other terminals de-allocating the assigned address and updating their database.

In this inventive aspect, autoconfiguration is provided on the assumption that all nodes will be assigned addresses from a single subnet. When a terminal powers up, it broadcasts a control message Address Request announcing its name. If no response is received within a time out period, it assumes that the terminal is the first terminal in the LAN and assigns an IP address by itself (e. g., the smallest IP address of the subnet, x. x. x. 1). On the other hand, if there are terminals already existing in the LAN, one of them (address allocating terminal) will issue an address. The address allocating terminal is the one having an address one less than the smallest address among the currently available unassigned addresses. If the smallest available address happens to be the

smallest IP address of the subnet, then the address allocating terminal will be the one having the smallest address among the terminals present. For example, if the currently available unassigned addresses are 10,20, and 30, then the next address allocating terminal will be the one with address 9 and the next address allocated will be 10. The role of the address allocating terminal may thus be assumed by different terminals for different requests, depending on the pattern of address allocation/de-allocation.

When the terminal gracefully leaves the network, the address will be de- allocated so that the address assigned can be re-claimed for further assignment.

This can be signaled using the detachment message explained later.

In essence, overall the present inventive aspects provide an alternative to the network routing of the prior art fixed and mobile networks. The solution proposed is to have terminals in the MANET adapted to act as data link layer (layer 2) bridges (as opposed to network layer routers) between other terminals that do not have a direct wireless link. Also, each terminal, acting as a bridge, will always broadcast control message for all other terminals, directly in range or indirectly via other in range bridges broadcasting to out of range nodes, to update themselves with current network information. The terminals/nodes conditionally act as bridges in accordance with stored criteria based on the current network information.

This broadcasting and updating enables the following required network functions: Path discovery; QoS-Quality of Service; Handoff, and; Autoconfiguration and service discovery.

Based on these functionalities, the packet forwarding in a MANET can be realised in an efficient manner.

DETAILED DESCRIPTION A preferred embodiment of the present invention will now be described with reference to the accompanying drawings, in which: Figure 1 illustrates an ad hoc network,

Figure 2 illustrates Intra-LAN Bridging, where'N'is a node, and'B'is a bridge, and Figure 3 illustrates Inter-LAN Bridging, where'B"is a bridge.

Approach In one aspect of the present invention, a terminal can either function as an end-user terminal or as a bridge or both. The terminal can be programmed to act in one of these modes. While acting as a bridge, it forwards the data link layer frames.

Control message is required to be propagated across the network for various functions such as the route discovery, auto-configuration etc. The control message is transmitted in a broadcast mode, using the inherent layer 2 broadcast capability of the wireless medium. The user data may be transmitted in a unicast, multicast, or broadcast mode, depending on the requirements.

Host information is fully distributed among the terminals and bridges. Each terminal/bridge maintains a table listing the host names/addresses and other key attributes.

Path Discovery A passive route (path) discovery is proposed. As opposed to the on- demand route discovery proposed in the ad hoc routing proposals of prior art MANETs, the availability of a mobile terminal will be announced by the terminal itself and this information will be broadcast across the entire network through intermediate bridges. All the terminals and bridges maintain this information and will be used for locating the terminals or for forwarding the packets to the terminal.

Only when the required information is unavailable, a terminal will query the information from the nearest terminal or bridge.

Control Information The path discovery is done by exchanging control information. It is conveyed using the following types of control messages: Attachment Detachment Query Response

Attachment Whenever a terminal enters the network, it broadcasts this Attachment message. All terminals and bridges in its vicinity update their host table which has the format shown below. If the terminal is in its direct vicinity, it enters"direct" under bridge information. The bridge (s) hearing this broadcast, re-broadcasts the message, by modifying the cost to reach the terminal through the bridge. The bridge also re-broadcasts this message to the radio cell from where it received.

This is to ensure that the hidden terminals also get the message. Other terminals, ignores the duplicate broadcast messages received. An attachment message could also be broadcast whenever a terminal notices that one or more bridges to which it could directly communicate with, are no longer reachable. In this case, this attachment message could possibly be relayed through a new set of bridges. All other terminals will update their host table according to the information contained in the new attachment message.

The cost could be a function of number of hops, delay involved in re- broadcasting, the duration for which the bridge will be active, loading of the bridge etc. If there are multiple bridges hearing the broadcast, every bridge will re- broadcast the message if the cost through the bridge is less than that is announced by other bridges. The terminals and bridges in the second radio cell will then update their host table by filling up the bridge column, cost, and other details. The bridges on the second and third radio cells, while computing the cost, announces the combined cost, including their own cost. This process continues from radio cell to radio cell and the information will be fully distributed across the entire network. The terminals and bridges need to check the duplicate messages received from other bridges.

The terminals/bridges use the following host table information for locating a terminal or for forwarding the packets.

Host Table Format Terminal Bridge Cost (Name/Address)

Attachment Message Format The following format may be used for this message: The field Cost will be empty when the terminal first broadcasts the attachment message. Bridges normally copy the information and add their own information before re- broadcasting. The terminal's address will be derived by the first bridge from the MAC frame. Similarly, the terminals/bridges hearing the subsequent re- broadcasts derive the previous terminal/bridge addresses. Src flag indicates whether the broadcast is from the terminal or from a bridge. This information can also be gathered by comparing the source address and the true source address. Source Destination Address Message Type Src flag True Source Cost Address (Broadcast) (Attachment) Address Detachment Whenever a mobile terminal leaves the network, it broadcasts this Detachment message. All terminals and bridges in its vicinity update their host table. One of the bridges re-broadcasts this message. If there are multiple bridges hearing the broadcast, one of the bridges relays this message and the remaining bridges keep quiet. The terminals and bridges in the second radio cell will update their host table. This process continues from radio cell to radio cell and the information will finally be fully distributed across the entire network. A bridge also re-broadcasts the message to the radio cell from where it received.

This is to ensure that the hidden terminals also get the information. The other terminals, ignores the duplicate broadcast messages received.

Detachment Message Format The following format may be used for this message: Source Address Destination Address Message Type True Source (Broadcast) (Detachment) Address Query/Response This is used to query the existence of a path to a terminal. If the designated terminal receives it, the terminal broadcasts a response. All the terminals and bridges that receive the response update their host table, if required. A bridge that holds the information about the designated terminal also broadcasts a response. If a terminal receives a response from both the

designated terminal and a bridge, it ignores the latter. If there is no response from the designated terminal and there is no bridge that holds the required information, then one of the bridges re-broadcasts the query to adjacent radio cells till it hits a bridge holding the relevant information or the designated terminal itself.

Query Message Format The following format may be used for this message: A bridge normally copies the information and adds its own information before re-broadcasting. The terminal's address will be derived by the first bridge from the MAC frame.

Similarly, the terminals/bridges hearing the subsequent re-broadcasts also derive the bridge address from the source address. Source Address Destination Address Message Type Terminal Address ( (Broadcast) (Query).

The bridge/designated terminal then initiates a response message similar to the attachment message and it propagates back to the entire network. If no response is received within the time out period, the terminal concludes that the designated terminal is unreachable.

The response could either be restricted or unrestricted. In restricted response, the response will be confined to the radio cell where it is currently attached. In this case, a simple message format as shown below, can be used.

In unrestricted response, the message could be broadcast to the neighboring radio cells as well, using an attachment Message. Source Address Destination Address Message Type (Broadcast) (Response) Once the path information is available, the subsequent user information (data packet) is sent along the path, also called packet forwarding. Different paths may be used for different packets to realise load balancing or to have improved QoS. The same packet may be sent through multiple paths (bridges) to improve the redundancy in case of loss or to improve the QoS.

Packet Forwarding The terminals use the information in the host table for sending data packets. If the destination is directly accessible to the source, the source puts the destination address in the data packet and sends it. If the destination is

accessible only through bridges, then the source puts the bridge address as the destination address and sends to a bridge. The bridge, then looks at the true destination address and modifies the destination address and forwards to the destination or to next bridge. This process continues until the data packet is received by the true destination.

Data Packets Source Address Destination Address Message_Type Dst-flag True Destination Address (Data) The source and destination addresses will be there in all data packets and control messages. The message type identifies whether it is a data packet or control message. The Dstftag identifies whether the data packet is to be bridged and if so, the next field specifies the true destination address for the data packet.

For bridged data packets, the bridge replaces the source address with its own address and destination address with the next bridge address or true destination address.

Advantages The proposed path discovery and packet forwarding techniques are considered to have the following advantages: Since broadcast takes minimum number of transmissions, the control information is propagated fast and disseminated to maximum number of terminals possible.

The number of path discoveries initiated to determine the presence or availability of a terminal by other terminals in the network, is minimised because of the terminal initiated path update.

Under normal conditions, no explicit end-to-end path discovery is involved for every packet forwarding session as done in ad hoc routing protocols, proposed in IETF MANET Working Group.

Path discovery is done by learning as in the case of wired LAN bridges.

Here the learning is limited only to attachment/detachment messages as opposed to every data link layer frame in the case of learning bridges.

Explicit detachment notification removes stale paths.

Terminals have the freedom to choose the one or more paths for forwarding packets during a session, based on QoS requirements.

Path information is propagated only in one direction (i. e., from destination to source)-as opposed to bi-directional path discovery process in MANET routing proposals (i. e., query from source to destination and acknowledgement in the reverse direction) The bridge need not check every packet to be forwarded as in traditional bridging. In this case, only those packets addressed to it need to be checked as in the case of routers.

The proposed technique improves the reachability to hidden terminals.

QoS Based Packet Forwarding A terminal has the information on the QoS supported by various paths.

The packet forwarding with some kind of QoS guarantee can be realised. The attachment message can carry relevant QoS information-like the number of hops, the accumulated delay across the path and so on. The bridges can be selected based on the QoS information. In addition, specific QoS control messages can be broadcast periodically by the bridges to have a dynamic control over QoS.

Handoff The handoff of mobile terminals can be realised as follows. When a mobile terminal moves from one radio cell to another, it first detaches from the current radio cell and then attaches to the new radio cell. Using this process, every other terminal in the network learns about the new path to the terminal and the packets will be forwarded accordingly. The packet loss during movement, if any, is assumed to be handled by the higher layer protocols.

Auto-configuration Another problem associated with prior art mobile ad hoc networks is that there is an absence of a centralised server. The present inventive aspect therefore provides distributed autoconfiguration and service discovery techniques for mobile ad hoc networks. As in the case of path discovery, the control message for auto-configuration and service discovery is also broadcast. This ensures reliability and fast distribution of control information.

A Simple Distributed IP Address Assignment Scheme for Ad hoc LANs Ad hoc Network with a single IP subnet address The assumption is that all nodes will be assigned addresses from a single subnet. When a terminal powers up, it broadcasts a control message Address Request announcing its name. If no response is received within a time out period, it assumes that the terminal is the first terminal in the LAN and assigns an IP address by itself (e. g., the smallest IP address of the subnet, x. x. x. 1). On the other hand, if there are terminals already existing in the LAN, one of them (address allocating terminal) will issue an address. The address allocating terminal is the one having an address one less than the smallest address among the currently available unassigned addresses. If the smallest available address happens to be the smallest IP address of the subnet, then the address allocating terminal will be the one having the smallest address among the terminals present.

The role of the address allocating terminal may thus be assumed by different terminals for different requests, depending on the pattern of address allocation/de-allocation.

When the terminal gracefully leaves the network by broadcasting the detachment message, the address will be de-allocated so that the address assigned can be re-claimed for further assignment.

Address Request Message Format Source Address Destination Address Message Type New Host Name Services (Broadcast) (Address Request) Address Allocation Message Format Source Destination Message Type New IPAddress New Host Address Address Address (Address Name Allocator Name (Broadcast)allocation Address Mapping Table Every terminal maintains this table. This table maintains the mapping between the terminal name, IP address, and the MAC address, and the services offered by the terminal. It is updated every time an address allocation takes place. Similarly, during address de-allocation, the table entry will be deleted.

Every time an allocation/de-allocation takes place, the terminal checks whether it is going to be the next address allocator.

Address Mapping Table Format Host Name MAC Address IP Address Services Infrastructure Mode The proposed scheme assumes an infrastructure-less network. However, the scheme works well in the case of an ad hoc network with fixed access point. It is assumed that the access point would have been established with a valid address even before the first terminal becomes active. Therefore, the very first address allocator will be the AP. Thereafter, the address allocation/de-allocation takes place as described earlier.

If a terminal is looking for the MAC address corresponding to a name/IP address, it broadcasts a query message. Its reply will be broadcast by the terminal. Thus, no special ARP requests need to be broadcast like in Ethernet.

Multiple IP Subnets Multiple subnets could be formed in the following cases: Two independent subnets get connected through a bridge The address space in a subnet overflows In this case, it also broadcasts a subnet formation message to all the neighbouring radio cells.

Advantages No ARP requests are needed.

Broadcast saves bandwidth.

Fully distributed, no centralised server is required as in the case of DHCP.

The server load is balanced among the terminals. The server node allocating the address is possibly different for different terminals.

Address space explosion is minimised by the re-use of address space.

The scheme works well in infrastructure and infrastructure-less modes.

Improved reliability and fast distribution of control information.

Error Conditions Name conflict : In case there is a name conflict, the address allocator sends a unicast error message asking the terminal to rename.

Unreachable : If a terminal is unable to send data packets, it sends out a query message and if there is no response within a time out period, the terminal initiates a forced recovery of the address assigned.

Mapping the algorithm and frame structures to existing wireless LANs IEEE 802.11 In the preferred embodiment disclosed, reference is made to IEEE 802.11.

In this case, the ACK needs to be disabled. The reason being, if the packet needs to be bridged, it will be immediately received by a bridge and an acknowledgement from the bridge does not make any sense to the sender.

However the RTS/CTS mechanism can continue to be there as the data packet transmission is point-to-point between the host and bridge.

It is also possible to carryout a similar adaptation of the algorithm to other wireless communication standards such Bluetooth, and Hiperlan.