Routing method for Ad-Hoc mobile networks

• US 5,987,011 A
• Filed: 08/30/1996
• Issued: 11/16/1999
• Est. Priority Date: 08/30/1996
• Status: Expired due to Fees

• Current Assignee: Chai-Keong Toh, King'S College
• Original Assignee: Chai-Keong Toh, King'S College
• Inventors: Toh, Chai Keong
• Primary Examiner(s): Pham, Chi H.
• Assistant Examiner(s): NGUYEN, STEVEN H D
• Application Number:
  US08/705,817
• Time in Patent Office: 1,173 Days
• Field of Search: 370/311, 370/312, 370/400, 370/401, 370/402, 370/369, 370/331, 370/256, 370/408, 370/428, 370/429, 370/468, 370/216, 370/255, 370/455, 370/228, 455/69, 455/523, 455/450, 455/452, 455/453, 455/509, 320/255, 320/256
• US Class Current: 370/331
• CPC Class Codes: H04W 40/10 based on available power or energy
• CPC Class Codes: H04W 40/24 Connectivity information management, e.g. connectivity discovery or connectivity update
• CPC Class Codes: H04W 48/08 Access restriction or access information delivery, e.g. discovery data delivery signalling during connection H04W76/00
• CPC Class Codes: H04W 48/16 Discovering, processing access restriction or access information
• CPC Class Codes: H04W 8/24 Transfer of terminal data
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks
• CPC Class Codes: Y02D 30/70 in wireless communication networks

Abstract

A routing method for supporting ad-hoc mobile communications within a radio communications network. The network comprises a plurality of mobile hosts including a source mobile host and a destination mobile host, and a plurality of radio communications links connecting together with mobile hosts. The method comprises measuring the stability of the communications links between neighbouring mobile hosts using an associativity based characteristic and selecting a communications route through the network from the source mobile host to the destination mobile host based on the stability of the communications links. The associativity characteristic is measured by each mobile host periodically transmitting and receiving identifier beacons (ticks) and updating the status of its corresponding links. The greater the number of ticks associated with a given link, the greater its stability. Use of the associativity characteristic enables the routing method to deal efficiently with mobile host migrations throughout the network.

Claims

1. A routing method for supporting ad-hoc mobile communications within a communications network, the network comprising a plurality of mobile hosts including a source mobile host and a destination mobile host and a plurality of wireless communication links connecting together said mobile hosts, said method comprising:

periodically transmitting an identifier signal by each of said plurality of mobile hosts in the network and receiving said identifier signals via said communication links between said mobile hosts;

measuring the stability of said communication links between said mobile hosts in accordance with the number of times said identifier signals are received from an associated mobile host via said communication links;

selecting a communications route through the network from the source mobile host to the destination mobile host based on the stability of said communications links; and

transmitting an information signal from said source mobile host across said network via said selected communications route to said destination mobile host,

wherein said step of selecting a communications route comprises

transmitting broadcast query signals from the source mobile host across the network;

appending route information to the broadcast query signals regarding the status of mobile hosts transmitting the broadcast query signals;

receiving and evaluating the broadcast query signals at the destination mobile host,

selecting a route through the network based on the stability of the communications links between mobile hosts; and

transmitting a route identifier signal along the selected route through the network from the destination mobile host to the source mobile host.

2. A routing method according to claim 1, wherein said communications links comprises radio frequency communication links.

3. A routing method according to claim 1, further comprising providing an associativity table at each mobile host, each said associativity table storing regularly updated information regarding the stability of each communications link between said mobile host and its associated mobile hosts.

4. A routing method according to claim 1, further comprising providing information relating to the forwarding delay of each said communications link between said mobile host and its associated mobile hosts.

5. A routing method according to claim 1, further comprising providing a routing table at each mobile host, each said routing table being configurable to set a route for passing said information signal through said mobile host from one of its said associated mobile hosts to others of its said associated mobile hosts.

6. A routing method according to claim 5, wherein each mobile host represents a node of the communications network and each said routing table stores information regarding a source node, a destination node, an incoming associated node, an outgoing associated node and the distance of said mobile host from the destination node.

7. A routing method according to claim 1, wherein the network supports a plurality of selected routes between respective source and destination mobile hosts, each mobile host in the network being able to handle a plurality of selected routes and being able to store route relaying load information regarding the total number of selected routes supported by said mobile host.

8. A routing method according to claim 7, wherein said step of selecting communications route also comprises considering the route relaying load information stored in the mobile hosts.

9. A routing method according to claim 1, further comprising:

providing a seen table at each mobile host, said seen table recording identifier data regarding an information signal which has passed through said mobile host; and

using said seen table to recognise and discard information signals that have previously been passed through said mobile host.

10. A routing method according to claim 1, wherein said information signal is provided in data packets, each data packet being arranged to hold routing information, control information and message information.

11. A routing method according to claim 1, further comprising providing a data flow acknowledgment mechanism comprising passive acknowledgments, each said passive acknowledgment comprising receiving at a mobile host an information signal previously sent by the mobile host to one of its associated mobile hosts and retransmitted back thereby.

12. A routing method according to claim 11, wherein said data flow acknowledgment mechanism further comprises active acknowledgments, each said active acknowledgment occurring when an information signal has reached its intended destination and retransmission would not occur passively, said active acknowledgment comprising the mobile host receiving an active retransmission of an information signal sent by the mobile host to its associated mobile host acting as the destination node.

13. A routing method according to claim 11 or 12, further comprising retransmitting said previously sent signal from said mobile host to said associated mobile host if a passive or active acknowledgment is not received within a predetermined time out period.

14. A routing method according to claim 1, further comprising:

appending quality of service information to the broadcast query signals, the quality of service information containing criteria on route selection which are taken into account on selecting a route through the network.

15. A routing method according to claim 1, wherein said route identifier signal configures mobile hosts along the selected route to pass forthcoming information signals between said source mobile host and said destination mobile host.

16. A routing method according to claim 1, further comprising reconstructing the selected route in response to a change in the stability of one said communication links indicating a broken communication link invalidating the selected route.

17. A routing method according to claim 16, wherein mobile hosts along the selected route are configured to pass forthcoming information signals between the source mobile host and the destination host and said step of reconstructing the selected route comprises:

identifying a pivot mobile host in the selected communications route adjacent the broken communication link;

transmitting a localised query signal from the pivot mobile host across the network;

appending route information to the localised query signal regarding the status of mobile hosts passing the localised query signal;

receiving and evaluating the localised query signals at the destination mobile host;

selecting a new partial route through the network from the pivot mobile host to the destination mobile host, the selection being based on the stability of the communications links therebetween; and

configuring mobile hosts along the new partial route to pass forthcoming information signals between the source mobile host and the destination mobile host.

18. A routing method according to claim 17, further comprising:

appending quality of service information to the localised query signal, the quality of service information containing criteria on route selection which are taken into account on selecting a route through the network.

19. A routing method according to claim 17, wherein said step of reconstructing the selected route further comprises:

reconfiguring the mobile hosts that were previously configured to be part of the selected route but which are not now part of the new partial route, to not be a part of the reconstructed selected route.

20. A routing method according to claim 16, wherein said step of reconstructing the selected route comprises:

transmitting broadcast query signals from the source mobile host across the network;

appending route information to the broadcast query signals regarding the status of mobile hosts passing the broadcast query signals;

receiving and evaluating the broadcast query signals at the destination mobile host;

selecting a route through the network based on the stability of the communications links between mobile hosts; and

transmitting a route identifier signal along the selected route through the network to the source mobile host.

21. A routing method according to claim 20, further comprising:

appending quality of service information to the broadcast query signals, the quality of service information containing criteria on route selection which are taken into account on selecting a route through the network.

22. A routing method according to claim 16, wherein said step of reconstructing the selected route further comprises:

(a) identifying a pivot mobile host in the selected communications route adjacent to the broken communication link;

(b) determining the distance between the identified pivot mobile host and the destination mobile host;

if the distance is greater than half the distance between the source mobile host and the destination mobile host,

transmitting a broadcast query signal from the source mobile host across the network;

appending route information to the broadcast query signal regarding the status of mobile hosts passing the broadcast query signals;

receiving and evaluating the broadcast query signal at the destination mobile host;

selecting a route through the network based on the stability of the communication links between the mobile hosts; and

transmitting a route identifier signal along the selected route through the network to the source mobile host;

or otherwise;

transmitting a localised query signal from the pivot mobile host across the network; and

appending route information to the localised query signal regarding the status of mobile hosts passing the localised query signal.

23. A routing method according to claim 22, wherein said step of reconstructing the selected route further comprises:

(c) determining whether the localised query signal is received by the destination mobile host within a predetermined time period;

if the localised query signal is received by the destination mobile host within the predetermined time period

evaluating the localised query signal at the destination mobile host-selecting a new partial route through the network form the pivot mobile host to the destination mobile host, the selection being based on the stability of the communication links therebetween and

configuring mobile hosts along the new partial route to pass forthcoming information signals between the source mobile host and the destination mobile host;

or otherwise;

identifying a new pivot mobile host in the selected communication route adjacent to the previous identified pivot mobile host, and carrying out step (b) on the basis of the new identified pivot mobile host.

24. A routing method according to claim 23, wherein step (c) is repeated until the destination mobile host either receives the localised query signal or the broadcast query signal.

25. A routing method according to claim 1, wherein mobile hosts along the selected route are configured to pass forthcoming information signals between the source mobile host and the destination host, further comprising deleting the selected route when it is no longer required, said deleting step comprising transmitting a deletion signal from the source mobile host across the network, said deletion signal reconfiguring each mobile host in the network.

26. A routing method according to claim 1, wherein said routing method is arranged for use with fixed base station wireless local area networks as a back-up communications system in case of base station failure.

27. A routing method according to claim 1, further comprising providing means for dynamically adjusting the transmission power of mobile hosts in the network in heavy usage conditions such that the number of relatively lightly-used communications links of a given mobile host can be reduced thereby increasing the throughput of said mobile host.

28. A routing method according to claim 1, further comprising discovering a new mobile host and incorporating the new host into the communication network, said incorporating step comprising:

detecting the presence of the new mobile host to any of the mobile hosts of the communications network by measuring the stability of said communication links between the new mobile host and an associated mobile host; and

establishing a communications link between the new mobile host and its associated mobile host.

29. A routing method according to claim 28, further comprising:

determining the services provided by the new mobile host; and

notifying the mobile hosts in the communications network of the discovery of the new mobile host and of the availability of its services.

30. In a base-station oriented wireless local area network comprising a plurality of mobile hosts, a wired network, a static host and a plurality of base stations, the static host and said base stations each being connected to the wired network, said base stations each having an associated wireless communications area within which the base station can communicate with one or more mobile hosts, and wherein said mobile host having established a first communications link with the static host via a first base station, migrates into a second wireless communications area of a second base station which is too heavily used to support a second communications link of the same bandwidth as the first, a method of re-establishing communications between said migrating mobile host and said static host, said method comprising:

establishing a second communications link between the mobile host and the static host via the second base station, said second communications link having a bandwidth which is reduced from that of the first communications link;

measuring the stability of the migrating mobile host with respect to said base stations using an associativity based characteristic; and

when the mobile host moves in to a new wireless communications area which is less heavily used than the second wireless communications area and the measured stability between the new base station and the mobile host is above a predetermined limit, establishing a new communications link between the mobile host and the static host via the new base station which has an increased bandwidth as compared to that of the second communications link.