Method and apparatus for dynamic neighbor discovery within wireless networks using time division multiple access (TDMA)

• US 7,502,360 B2
• Filed: 03/04/2005
• Issued: 03/10/2009
• Est. Priority Date: 03/04/2005
• Status: Expired due to Fees

• Current Assignee: Stingray IP Solutions LLC (Acacia Research Corporation)
• Original Assignee: ITT Manufacturing Enterprises, Inc. (ITT, Inc.)
• Inventors: Wetstein, Robert, Liu, Yu-Jih
• Primary Examiner(s): Appiah, Charles N
• Assistant Examiner(s): CONTEE, JOY KIMBERLY
• Application Number:
  US11/071,235
• Publication Number:
  US 20060198346A1
• Time in Patent Office: 1,467 Days
• Field of Search: 370/445, 370/346, 370/278, 370/458
• US Class Current: 370/348
• CPC Class Codes: H04W 40/24 Connectivity information management, e.g. connectivity discovery or connectivity update

Abstract

An Ad-Hoc wireless network according to the present invention employs a TDMA based neighbor discovery protocol, where each network node is assigned a unique time slot to broadcast neighbor discovery packets or messages. A primary controller node is dynamically designated to perform the time slot assignments. A dynamic selection of a secondary or backup controller node is further provided in case of failure of the primary controller node. The present invention further includes flooding techniques based upon TDMA. A TDMA HELLO flood is used to distribute a small number of common parameters to network nodes by placing or piggybacking the information within the neighbor discovery messages. A CNR flood is based on the principles of a RAKE type receiver and used to distribute time slot assignments to the entire network.

Claims

1. A communication unit to transmit and receive information within a communications network and to discover neighboring communication units comprising:

a transmitter to transmit outgoing information to at least one other communication unit within said network;

a receiver to receive incoming information from at least one other communication unit within said network; and

a processor to control said transmission and reception of said outgoing and incoming information, wherein said processor includes;

a neighbor discovery module to transmit neighbor discovery messages to neighboring communication units in accordance with a time division multiplexing communication scheme and a second different communication scheme, wherein neighbor discovery messages are transmitted within an assigned time slot in said time division multiplexing communication scheme to indicate the presence of said communication unit within said network; and

a controller module to assign and maintain said communication scheme time slots for said communication units within said network in response to said communication unit being selected as a primary controller.

2. The unit of claim 1, wherein said time division multiplexing communication scheme includes time division multiple access (TDMA).

3. The unit of claim 1, wherein said transmitter transmits said outgoing information in the form of radio signals.

4. The unit of claim 1, wherein said receiver receives said incoming information in the form of radio signals.

5. The unit of claim 1, wherein said processor further includes:

an initial discovery module to transmit neighbor discovery messages in accordance with said second communication scheme different from said time division multiplexing scheme to indicate the presence of said communication unit within said network.

6. The unit of claim 5, wherein said second communication scheme includes Carrier Sense Multiple Access (CSMA).

7. The unit of claim 1, wherein said processor further includes:

a primary controller selection module to dynamically select a communication unit within said network to serve as said primary controller.

8. The unit of claim 7, wherein each said communication unit within said network includes an identification and said primary controller selection module includes an identification module to compare identifications of communication units and select said primary controller based on said comparison.

9. The unit of claim 7, wherein said processor further includes:

a secondary controller selection module to dynamically select a communication unit within said network to serve as a secondary controller to assign and maintain said communication scheme time slots for said communication units within said network in response to disablement of said primary controller.

10. The unit of claim 9, wherein said secondary controller selection module includes an identification module to compare identifications of communication units and select said secondary controller based on said comparison and connectivity of communication units to said network.

11. The unit of claim 5, wherein said processor further includes:

a discovery termination module to terminate utilization of said second communication scheme for neighbor discovery in favor of said time division multiplexing communication scheme.

12. The unit of claim 11, wherein said discovery termination module includes a condition module to terminate utilization of said second communication scheme in response to selection of a controller to assign and maintain said communication scheme time slots and the absence of a change in said controller within a predetermined time interval.

13. The unit of claim 1, wherein said controller module includes a static assignment module to assign said time slots in a static fashion to said communication units.

14. The unit of claim 1, wherein said controller module includes a dynamic assignment module to assign said time slots and adjust a period of said time division multiplexing communication scheme in a dynamic fashion.

15. The unit of claim 14, wherein said dynamic assignment module includes a time slot module to assign time slots to each communication unit based on a hop distance between that communication unit and said primary controller.

16. The unit of claim 14, wherein said time division multiplexing communication scheme includes a time division multiplexing architecture including a plurality of epochs each with a series of time slots, and said dynamic assignment module includes a period adjustment module to dynamically adjust said quantity of epochs within said architecture to accommodate said communication units within said network.

17. The unit of claim 1, wherein said controller module includes a flood module to transmit said time slot assignments to said communication units, wherein said time slot assignments are transmitted to enable constructive superposition to remove multi-path interference and enhance signal strength.

18. The unit of claim 1, wherein said neighbor discovery module includes:

a neighbor detect module to detect the presence of a new neighboring communication unit in response to receiving a neighbor discovery message in a corresponding time slot assigned to that neighboring communication unit; and

a lost neighbor module to detect the absence of a neighboring communication unit in response to a lack of reception of said neighbor discovery message in a corresponding time slot assigned to that neighboring communication unit.

19. A method of transferring information between a communication unit and other units within a communications network and discovering neighboring communication units comprising:

(a) transmitting neighbor discovery messages from said communication unit to neighboring communication units in accordance with a time division multiplexing communication scheme and a second different communication scheme, wherein neighbor discovery messages are transmitted within an assigned time slot in said time division multiplexing communication scheme to indicate the presence of said communication unit within said network; and

(b) assigning and maintaining said communication scheme time slots for said communication units within said network in response to said communication unit being selected as a primary controller.

20. The method of claim 19, wherein said time division multiplexing communication scheme includes time division multiple access (TDMA).

21. The method of claim 20, wherein said neighbor discovery messages are transmitted in the form of radio signals.

22. The method of claim 19, wherein step (a) further includes:

(a.1) transmitting initial neighbor discovery messages from said communication unit in accordance with said second communication scheme different from said time division multiplexing scheme to indicate the presence of said communication unit within said network.

23. The method of claim 22, wherein said second communication scheme includes Carrier Sense Multiple Access (CSMA).

24. The method of claim 19, wherein step (a) further includes:

(a.1) dynamically selecting a communication unit within said network to serve as said primary controller.

25. The method of claim 24, wherein each said communication unit within said network includes an identification, and step (a.1) further includes:

(a.1.1) comparing identifications of communication units and selecting said primary controller based on said comparison.

26. The method of claim 24, wherein step (a) further includes:

(a.2) dynamically selecting a communication unit within said network to serve as secondary controller to assign and maintain said communication scheme time slots for said communication units within said network in response to disablement of said primary controller.

27. The method of claim 26, wherein step (a.2) further includes:

(a.2.1) comparing identifications of communication units and selecting said secondary controller based on said comparison and connectivity of communication units to said network.

28. The method of claim 22, wherein step (a) further includes:

(a.2) terminating utilization of said second communication scheme for neighbor discovery in favor of said time division multiplexing communication scheme.

29. The method of claim 28, wherein step (a.2) further includes:

(a.2.1) terminating utilization of said second communication scheme in response to selection of a controller to assign and maintain said communication scheme time slots and the absence of a change in said controller within a predetermined time interval.

30. The method of claim 19, wherein step (b) further includes:

(b.1) assigning said time slots in a static fashion to said communication units.

31. The method of claim 19, wherein step (b) further includes:

(b.1) assigning said time slots and adjusting a period of said time division multiplexing communication scheme in a dynamic fashion.

32. The method of claim 31, wherein step (b.1.1) further includes:

(b.1.1) assigning time slots to each communication unit based on a hop distance between that communication unit and said primary controller.

33. The method of claim 31, wherein said time division multiplexing communication scheme includes a time division multiplexing architecture including a plurality of epochs each with a series of time slots, and step (b.1) further includes:

(b.1.1) dynamically adjusting said quantity of epochs within said architecture to accommodate said communication units within said network.

34. The method of claim 19, wherein step (b) further includes:

(b.1) transmitting said time slot assignments to said communication units, wherein said time slot assignments are transmitted to enable constructive superposition to remove multi-path interference and enhance signal strength.

35. The method of claim 19, wherein step (a) further includes:

(a.1) detecting the presence of a new neighboring communication unit in response to receiving a neighbor discovery message in a corresponding time slot assigned to that neighboring communication unit; and

(a.2) detecting the absence of a neighboring communication unit in response to a lack of reception of said neighbor discovery message in a corresponding time slot assigned to that neighboring communication unit.

36. A communications network comprising:

a plurality of communication units for transferring information therebetween, wherein neighbor discovery messages are transmitted from said communication units to neighboring communication units in accordance with a time division multiplexing communication scheme and a second different communication scheme, wherein neighbor discovery messages are transmitted within assigned time slots in said time division multiplexing communication scheme to indicate the presence of said communication units within said network, and wherein one of said communication units is designated as a primary controller to assign and maintain said communication scheme time slots for said communication units within said network.

37. The network of claim 36, wherein said time division multiplexing communication scheme includes time division multiple access (TDMA).

38. The network of claim 36, wherein initial neighbor discovery messages are transmitted from said communication units in accordance with said second communication scheme different from said time division multiplexing scheme to indicate the presence of said communication units within said network.

39. The network of claim 38, wherein said second communication scheme includes Carrier Sense Multiple Access (CSMA).

40. The network of claim 36, wherein said communication units dynamically select a communication unit within said network to serve as said primary.

41. The network of claim 40, wherein said communication units dynamically select a communication unit within said network to serve as a secondary controller to assign and maintain said communication scheme time slots for said communication units within said network in response to disablement of said primary controller.

42. The network of claim 38, wherein said communication units terminate utilization of said second communication scheme for neighbor discovery in favor of said time division multiplexing communication scheme.

43. The network of claim 40, wherein said primary controller assigns said time slots and adjusts a period of said time division multiplexing communication scheme in a dynamic fashion.

44. The network of claim 36, wherein said communication units detect the presence of a new neighboring communication unit in response to receiving a neighbor discovery message in a corresponding time slot assigned to that neighboring communication unit, and wherein said communication units detect the absence of a neighboring communication unit in response to a lack of reception of said neighbor discovery message in a corresponding time slot assigned to that neighboring communication unit.

45. A method of transferring information between communication units within a communications network and discovering neighboring communication units comprising:

(a) transmitting neighbor discovery messages from said communication units to neighboring communication units in accordance with a time division multiplexing communication scheme and a second different communication scheme, wherein neighbor discovery messages are transmitted within assigned time slots in said time division multiplexing communication scheme to indicate the presence of said communication units within said network; and

(b) assigning and maintaining said communication scheme time slots for said communication units within said network via one of said communication units designated as a primary controller.

46. The method of claim 45, wherein said time division multiplexing communication scheme includes time division multiple access (TDMA).

47. The method of claim 45, wherein step (a) further includes:

(a.1) transmitting initial neighbor discovery messages from said communication units in accordance with said second communication scheme different from said time division multiplexing scheme to indicate the presence of said communication units within said network.

48. The method of claim 47, wherein said second communication scheme includes Carrier Sense Multiple Access (CSMA).

49. The method of claim 45, wherein step (a) further includes:

(a.1) dynamically selecting a communication unit within said network to serve as said primary controller.

50. The method of claim 49, wherein step (a) further includes:

(a.2) dynamically selecting a communication unit within said network to serve as a secondary controller to assign and maintain said communication scheme time slots for said communication units within said network in response to disablement of said primary controller.

51. The method of claim 47, wherein step (a) further includes:

(a.2) terminating utilization of said second communication scheme for neighbor discovery in favor of said time division multiplexing communication scheme.

52. The method of claim 49, wherein step (a) further includes:

(a.2) assigning said time slots and adjusting a period of said time division multiplexing communication scheme in a dynamic fashion via said primary controller.

53. The method of claim 45, wherein step (a) further includes:

(a.1) detecting the presence of a new neighboring communication unit in response to receiving a neighbor discovery messge in a corresponding time slot assigned to that neighboring communication unit; and

(a.2) detecting the absence of a neighboring communication unit in response to a lack of reception of said neighbor discovery message in a corresponding time slot assigned to that neighboring communication unit.