System and method to assure node connectivity in an ad hoc network

• US 7,512,079 B2
• Filed: 07/28/2005
• Issued: 03/31/2009
• Est. Priority Date: 07/28/2004
• Status: Expired due to Fees

• Current Assignee: University of South Florida (State University System of Florida)
• Original Assignee: University of South Florida (State University System of Florida)
• Inventors: Ramarathinam, Venkatesh, Labrador, Miguel A.
• Primary Examiner(s): Shah; Chirag G
• Assistant Examiner(s): Zhou; Yong
• Application Number:
  US11/161,272
• Publication Number:
  US 20060023677A1
• Time in Patent Office: 1,342 Days
• Field of Search: 370/252, 370/254, 370/255, 370/312, 370/315, 370/332, 370/338, 455/134, 455/436, 455/522, 455/561
• US Class Current: 370/254
• CPC Class Codes: H04L 45/42 Centralised routing
• CPC Class Codes: H04W 40/10 based on available power or energy
• CPC Class Codes: H04W 40/12 based on transmission quality or channel quality
• CPC Class Codes: H04W 40/30 for proactive routing
• CPC Class Codes: H04W 8/005 Discovery of network devices, e.g. terminals
• 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

In accordance with the present invention is provided, a method to assure node connectivity in an ad hoc wireless network comprising a wireless main controller, a plurality of wireless nodes having a plurality of neighboring nodes and a plurality of wireless links connecting the wireless main controller, the plurality of wireless nodes and the plurality of neighboring nodes. The proposed method includes, computing a composite threshold for each of a plurality of neighboring nodes of a plurality of nodes, assigning a mobility to each of the plurality of nodes based on the composite threshold for each of the plurality of neighboring node and using the mobility assigned to each of the plurality of nodes to assure node connectivity in the ad hoc network.

Claims

1. A method to assure node connectivity in an ad hoc wireless network comprising a wireless main controller, a plurality of wireless nodes having a plurality of neighboring nodes and a plurality of wireless links connecting the wireless main controller, the plurality of wireless nodes and the plurality of neighboring nodes, the method comprising:

computing a composite threshold for each of a plurality of neighboring nodes of a plurality of nodes, wherein computing the composite threshold further comprises;

identifying an energy level and a signal power level for each of the plurality of nodes;

determining a weighting factor;

identifying a normalized energy level for each of the plurality of neighboring nodes;

identifying a normalized signal power level for each of the plurality of neighboring nodes;

calculating the composite threshold for each of the neighboring nodes based on the relationship;

composite threshold=(weighting factor*normalized energy level)+(1-weighting factor)*normalized signal power level)

assigning a mobility to each of the plurality of nodes based on the composite threshold for each of the plurality of neighboring nodes; and

using the mobility assigned to each of the plurality of nodes to assure node connectivity in the ad hoc network.

2. The method of claim 1, wherein the composite threshold for each of a plurality of neighboring nodes of a plurality of nodes is computed at each of the plurality of nodes and the composite threshold for each of the plurality of neighboring nodes is transmitted to a main controller.

3. The method of claim 1, wherein the composite threshold for each of a plurality of neighboring nodes of a plurality of nodes is computed at a main controller.

4. The method of claim 1, wherein the mobility is assigned to each of the plurality of nodes at each of the plurality of nodes.

5. The method of claim 1, wherein the mobility is assigned to each of the plurality of nodes at a main controller and the assigned mobility is transmitted to each of the plurality of nodes.

6. The method of claim 1, wherein the step of computing a composite threshold for each of a plurality of neighboring nodes further comprises:

transmitting a hello signal from each of the plurality of nodes, the hello signal comprising the energy level and the signal power level;

receiving the plurality of transmitted hello signals at each of the plurality of nodes, the plurality of transmitted hello signals received from each of the plurality of neighboring nodes;

identifying the signal power level and the energy level for each of the plurality of transmitted hello signals received from each of the plurality of neighboring nodes;

accessing an information table stored at each of the plurality of nodes; and

computing the composite threshold for each of the neighboring nodes based on the information table.

7. The method of claim 6, wherein the information table further comprises an entry for each of the plurality of neighboring nodes, a corresponding entry for the normalized energy level for each of the plurality of neighboring nodes and a corresponding entry for the normalized signal power level at which the hello packet was received from each of the neighboring nodes.

8. The method of claim 6, wherein the step of computing a composite threshold for each of the neighboring nodes further comprises measuring the quality and stability of a wireless connection between a node and each of the neighboring nodes.

9. The method of claim 1, wherein the normalized energy level is equal to a ratio of the energy level of each of the plurality of neighboring nodes to a predetermined maximum possible energy level for the node.

10. The method of claim 1, wherein the normalized signal power level is equal to a ratio of the signal power level of each of the plurality of neighboring nodes to a predetermined maximum possible signal power level for the node.

11. The method of claim 9, wherein the predetermined maximum possible energy level for the node is equal to the energy value of a node battery when fully charged.

12. The method of claim 10, wherein the predetermined maximum possible signal power level for the node is equal to the signal power level between two nodes in close proximity and assuming ideal transmission conditions.

13. The method of claim 1, wherein the weighting factor is a dynamic weighting factor based on current network behavior.

14. The method of claim 1, wherein the weighting factor is a static weighting factor.

15. The method of claim 6, further comprising the step of storing the composite threshold for each of the neighboring nodes in an update table at each of the plurality of nodes and transmitting the update table from each of the plurality of nodes to the main controller.

16. The method of claim 15, wherein the update table comprises an entry for each of the plurality of neighboring nodes and a corresponding entry for the composite threshold for each of the plurality of neighboring nodes.

17. The method of claim 1, wherein the method to assure node connectivity is a control layer method operating between a routing layer and a data link layer.

18. The method of claim 17, wherein the routing layer utilizes an ad hoc on-demand distance vector (AODV) protocol.

19. The method of claim 17, wherein the data link layer is an IEEE 802.11b MAC protocol.

20. The method of claim 1, wherein the plurality of neighboring nodes are identified from the plurality of nodes as being within a transmission range of each of the plurality of nodes.

21. The method of claim 1, wherein the step of computing a composite threshold for each of the plurality of neighboring nodes is repeated at a predetermined interval.

22. The method of claim 1, wherein the step of assigning a mobility to each of the plurality of nodes based on the composite threshold for each of the plurality of neighboring nodes is repeated at a predetermined interval.

23. The method of claim 1, wherein the step of assigning a mobility to each of the plurality of nodes based on the composite threshold for each of the plurality of neighboring nodes further comprises:

evaluating the composite threshold for each of the plurality of neighboring nodes received from each of the plurality of nodes to determine if each of the plurality of nodes has a link connection to the main controller; and

assigning a mobility to stop the movement of the node if the node if is determined to not have a link connection to the main controller.

24. The method of claim 23, wherein the link connection between the node and the main controller is a direct connection.

25. The method of claim 23, wherein the link connection between the node and the main controller is through a safe neighbor connection.

26. The method of claim 23, wherein a link connection is identified as being a link connection above the composite threshold for the node.

27. The method of claim 23, wherein the mobility is assigned to restart the movement of the node if the node is determined to have a link connection to the main controller.

28. The method of claim 23, wherein the mobility is assigned to request that the node move closer to the main controller.

29. A system to assure node connectivity in an ad hoc wireless network comprising a wireless main controller, a plurality of wireless nodes having a plurality of neighboring nodes and a plurality of wireless links connecting the wireless main controller, the plurality of wireless nodes and the plurality of neighboring nodes, the system comprising:

means for computing a composite threshold for each of a plurality of neighboring nodes of a plurality of nodes, wherein the means for computing a composite threshold further comprises means for;

identifying an energy level and a signal power level for each of the plurality of nodes;

determining a weighting factor;

identifying a normalized energy level for each of the plurality of neighboring nodes;

identifying a normalized signal power level for each of the plurality of neighboring nodes;

calculating the composite threshold for each of the neighboring nodes based on the relationship;

composite threshold=(weighting factor*normalized energy level)+(1-weighting factor)*normalized signal power level); and

means for assigning a mobility to each of the plurality of nodes based on the composite threshold for each of the plurality of neighboring nodes; and

means for using the mobility assigned to each of the plurality of nodes to assure node connectivity in the ad hoc network.

30. The system of claim 29, wherein the plurality of nodes for computing the composite threshold for each of a plurality of neighboring nodes further comprises:

means for transmitting a hello signal from each of the plurality of nodes, the hello signal comprising the energy level and the signal power level;

means for receiving a plurality of transmitted hello signals at each of the plurality of nodes, the plurality of transmitted hello signals received from each of the plurality of neighboring nodes;

means for identifying the signal power level and the energy level for each of the plurality of transmitted hello signals received from each of the plurality of neighboring nodes;

means for accessing an information table stored at each of the plurality of nodes;

means for computing a composite threshold for each of the neighboring nodes based on the information table; and

means for storing the composite threshold for each of the neighboring nodes in an update table at each of the plurality of nodes and transmitting the update table from each of the plurality of nodes to the main controller.

31. The system of claim 29, wherein the means for assigning a mobility to each of the plurality of nodes based on the composite threshold for each of the plurality of neighboring nodes further comprises:

means for evaluating the update table received from each of the plurality of nodes to determine if each of the plurality of nodes has a link connection to the main controller; and

means for assigning a mobility to a node based on the link connection to the main controller.

32. A system to assure node connectivity in an ad hoc wireless network comprising a wireless main controller, a plurality of wireless nodes having a plurality of neighboring nodes and a plurality of wireless links connecting the wireless main controller, the plurality of wireless nodes and the plurality of neighboring nodes, the system comprising:

a plurality of nodes for computing a composite threshold for each of a plurality of neighboring nodes and transmitting the composite threshold for each of a plurality of neighboring nodes to a main controller, wherein the composite threshold is computed by;

identifying an energy level and a signal power level for each of the plurality of nodes;

determining a weighting factor;

identifying a normalized energy level for each of the plurality of neighboring nodes;

identifying a normalized signal power level for each of the plurality of neighboring nodes;

calculating the composite threshold for each of the neighboring nodes based on the relationship;

composite threshold=(weighting factor*normalized energy level)+(1-weighting factor)*normalized signal power level); and

a main controller for assigning a mobility to each of the plurality of nodes based on the composite threshold for each of the plurality of neighboring nodes and transmitting the assigned mobility to each of the plurality of nodes to assure node connectivity in the ad hoc network.

33. A computer readable medium for providing instructions for directing a processor to carry out a method to assure node connectivity in an ad hoc wireless network comprising a wireless main controller, a plurality of wireless nodes having a plurality of neighboring nodes and a plurality of wireless links connecting the wireless main controller, the plurality of wireless nodes and the plurality of neighboring nodes, the instructions including steps for computing a composite threshold for each of a plurality of neighboring nodes by identifying an energy level and a signal power level for each of the plurality of nodes, determining a weighting factor, identifying a normalized energy level for each of the plurality of neighboring nodes, identifying a normalized signal power level for each of the plurality of neighboring nodes, calculating the composite threshold for each of the neighboring nodes based on the relationship:

composite threshold=(weighting factor*normalized energy level)+(1-weighting factor)*normalized signal power level), and transmitting the composite threshold for each of a plurality of neighboring nodes and means for assigning a mobility to each of the plurality of nodes based on the composite threshold for each of the plurality of neighboring nodes and transmitting the assigned mobility to each of the plurality of nodes to assure node connectivity in the ad hoc network.