Energy efficient forwarding in ad-hoc wireless networks

• US 7,979,096 B1
• Filed: 10/16/2008
• Issued: 07/12/2011
• Est. Priority Date: 11/30/2001
• Status: Expired due to Fees

• Current Assignee: III Holdings 1, LLC
• Original Assignee: Tri-County Excelsior Foundation (Oso IP, LLC)
• Inventors: Elliott, Brig Barnum, Pearson, David Spencer
• Primary Examiner(s): Edouard, Patrick N
• Assistant Examiner(s): Perez, Julio
• Application Number:
  US12/253,130
• Time in Patent Office: 999 Days
• Field of Search: 455/574, 455/343.2, 455/343.4, 709/237
• US Class Current: 455/572
• CPC Class Codes: H04J 3/16 in which the time allocation to individual channels within a transmission cycle is variable, e.g. to accommodate varying complexity of signals, to vary number of channels transmitted H04J3/17, H04J3/24 take precedence
• CPC Class Codes: H04W 52/0216 using a pre-established activity schedule, e.g. traffic indication frame
• CPC Class Codes: H04W 52/0219 where the power saving management affects multiple terminals
• CPC Class Codes: H04W 56/00 Synchronisation arrangements
• CPC Class Codes: H04W 72/12 Wireless traffic scheduling
• CPC Class Codes: H04W 72/20 Control channels or signalling for resource management
• 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 system for conserving energy in a multi-node network (110) includes nodes (205) configured to organize themselves into tiers (305, 310, 315). The nodes (205) are further configured to produce a transmit/receive schedule at a first tier (310) in the network (110) and control the powering-on and powering-off of transmitters and receivers in nodes (205) in a tier adjacent (315) to the first tier (310) according to the transmit/receive schedule.

Claims

1. An apparatus with a non-transitory device-readable medium encoded with instructions, comprising:

instructions capable of being used to cause storage of first data comprising one or more identifiers associated with one or more children nodes affiliated with a parent node in a network;

instructions capable of being used to cause storage of second data comprising a first time schedule for communication of one or more first messages from the parent node to at least one of the one or more affiliated children nodes and a second time schedule for communication of one or more second messages to the parent node from at least one of the one or more affiliated children nodes;

instructions capable of being used to cause storage of third data comprising an identifier associated with the parent node;

instructions capable of being used to cause message communication, the message communication capable of being caused using the first data, the third data, and the second data comprising the first time schedule for communication of one or more first messages from the parent node to at least one of the one or more affiliated children nodes and the second time schedule for communication of one or more second messages to the parent node from at least one of the one or more affiliated children nodes, wherein the apparatus is configured such that a manner of the message communication is caused for power saving purposes by allowing at least one of the one or more affiliated children nodes to sleep, utilizing at least one of the first data or the second data;

instructions capable of being used to cause communication of a scheduling message including at least one of the first data or the second data between the parent node and at least one of the one or more affiliated children nodes; and

instructions capable of being used to cause a plurality of child/parent time slots associated with different ones of the affiliated children nodes to be temporally grouped together, wherein the apparatus is configured to cause the plurality of child/parent time slots associated with the different ones of the affiliated children nodes to be temporally adjacent.

2. The apparatus set forth in claim 1, further comprising:

instructions capable of being used to cause storage of fourth data comprising a time schedule allocating times for the affiliated children nodes.

3. The apparatus set forth in claim 1, further comprising:

instructions capable of being used to cause storage of fourth data comprising a time schedule allocating times for the affiliated children nodes to transmit third messages to, or receive fourth messages from, other children nodes.

4. The apparatus set forth in claim 1, wherein at least one of the one or more affiliated children nodes includes one or more sensor nodes.

5. The apparatus set forth in claim 1, wherein the apparatus is part of a system that includes a computer.

6. The apparatus set forth in claim 1, wherein the instructions capable of being used to cause storage of first data, the instructions capable of being used to cause storage of second data, and the instructions capable of being used to cause storage of third data, are software.

7. The apparatus set forth in claim 1, wherein the instructions capable of being used to cause storage of first data, the instructions capable of being used to cause storage of second data, and the instructions capable of being used to cause storage of third data, are embodied in hardware.

8. The apparatus set forth in claim 1, further comprising instructions capable of being used to cause at least one of the one or more affiliated children nodes to sleep, utilizing at least one of the first data or the second data.

9. The apparatus set forth in claim 1, wherein the instructions capable of being used to cause the message communication are adapted for use in an ad-hoc wireless network.

10. The apparatus set forth in claim 1, wherein the instructions capable of being used to cause the message communication are adapted for use in a multi-tier wireless network capable of including at least three tiers.

11. The apparatus set forth in claim 1, wherein the message communication includes transmitting the one or more first messages.

12. The apparatus set forth in claim 1, wherein the message communication includes receiving the one or more second messages.

13. The apparatus set forth in claim 1, wherein the apparatus is configured such that the scheduling message is communicated periodically.

14. The apparatus set forth in claim 1, wherein the apparatus is configured such that the scheduling message is communicated via a carrier sense multiple access (CSMA) technique.

15. The apparatus set forth in claim 1, further comprising instructions capable of being used to allow receipt of acknowledgements in response to the communication of the scheduling message.

16. The apparatus set forth in claim 1, wherein the apparatus is configured to operate as at least one of the affiliated children nodes and is configured to cooperate with an acoustic sensor.

17. The apparatus set forth in claim 1, wherein the apparatus is configured to operate as at least one of the affiliated children nodes and is configured to cooperate with a motion-detection sensor.

18. The apparatus set forth in claim 1, wherein the apparatus is configured to operate as at least one of the affiliated children nodes and is configured to cooperate with a radar sensor.

19. The apparatus set forth in claim 1, wherein the apparatus is configured to operate as at least one of the affiliated children nodes and is configured to cooperate with a sensor that detects one or more chemicals.

20. The apparatus set forth in claim 1, wherein the apparatus is configured to operate as at least one of the affiliated children nodes and is configured to cooperate with a visual sensor.

21. The apparatus set forth in claim 1, wherein the apparatus is configured to operate as at least one of the affiliated children nodes includes a visual sensor that is capable of being used to record moving images.

22. The apparatus set forth in claim 1, wherein the apparatus is configured to operate as at least one of the affiliated children nodes and is configured to cooperate with a thermal sensor.

23. The apparatus set forth in claim 1, wherein the apparatus is configured to operate as at least one of the affiliated children nodes and is configured to cooperate with a sensor that detects nuclear radiation or a biological agent.

24. The apparatus set forth in claim 1, wherein the network includes a local area network.

25. The apparatus set forth in claim 1, wherein the apparatus is operable to buffer data.

26. The apparatus set forth in claim 1, wherein the apparatus is configured to operate as the parent node and is included as a component of a system.

27. The apparatus set forth in claim 26, wherein the system further includes a plurality of the affiliated children nodes.

28. The apparatus set forth in claim 27, wherein at least one of the affiliated children nodes includes an acoustic sensor.

29. The apparatus set forth in claim 27, wherein at least one of the affiliated children nodes includes a motion-detection sensor.

30. The apparatus set forth in claim 27, wherein at least one of the affiliated children nodes includes a radar sensor.

31. The apparatus set forth in claim 27, wherein at least one of the affiliated children nodes includes a sensor that detects one or more chemicals.

32. The apparatus set forth in claim 27, wherein at least one of the affiliated children nodes includes a visual sensor.

33. The apparatus set forth in claim 27, wherein at least one of the affiliated children nodes includes a visual sensor that is capable of being used to record moving images.

34. The apparatus set forth in claim 27, wherein at least one of the affiliated children nodes includes a thermal sensor.

35. The apparatus set forth in claim 27, wherein at least one of the affiliated children nodes includes a sensor that detects nuclear radiation or a biological agent.

36. The apparatus set forth in claim 1, further comprising instructions for allowing receipt of acknowledgements in response to the communication of information.

37. The apparatus set forth in claim 1, further comprising instructions capable of being used to allow receipt, at a particular node, a first powering-on schedule from another node in the network.

38. The apparatus set forth in claim 37, further comprising instructions capable of being used to selectively power-on at least one of a transmitter or a receiver based on the received first powering-on schedule.

39. The apparatus set forth in claim 38, further comprising instructions capable of being used to cause production of a second powering-on schedule based on the first powering-on schedule.

40. The apparatus set forth in claim 39, further comprising instructions capable of being used to cause transmission of the second powering-on schedule from the particular node to one or more other nodes in the network.

41. The apparatus set forth in claim 39, further comprising instructions capable of being used to cause transmission of the second powering-on schedule from the particular node to one or more other nodes in the network when the transmitter is in a powered-on state.

42. The apparatus set forth in claim 1, wherein the network comprises an ad-hoc, multi-node wireless network.

43. The apparatus set forth in claim 1, wherein the network comprises a wireless sensor network.

44. The apparatus set forth in claim 1, further comprising instructions capable of being used to cause organization of the network into a hierarchy of tiers.

45. The apparatus set forth in claim 44, wherein the network includes a sensor network.

46. The apparatus set forth in claim 44, further comprising instructions capable of being used to cause communication of the scheduling message throughout the network.

47. The apparatus set forth in claim 46, wherein the scheduling message includes a transmit scheduling message.

48. The apparatus set forth in claim 46, wherein the scheduling message includes a receive scheduling message.

49. The apparatus set forth in claim 46, further comprising instructions capable of being used to cause transmission or receipt of data messages between nodes in adjacent tiers based on the scheduling message.

50. The apparatus set forth in claim 46, wherein the scheduling message comprises time schedules for powering-on and powering-off transmitters and receivers at each of a plurality of nodes in adjacent tiers.

51. The apparatus set forth in claim 46, wherein the scheduling message comprises time schedules for powering-on transmitters or receivers at each of a plurality of nodes in adjacent tiers.

52. The apparatus set forth in claim 44, wherein the apparatus is operable such that at least one child node in a tier of the network receives third messages from children nodes in a higher tier.

53. The apparatus set forth in claim 52, wherein the third messages include data messages.

54. The apparatus set forth in claim 53, wherein a destination of the data messages comprises at least one data collection point.

55. The apparatus set forth in claim 54, wherein the at least one data collection point resides in a lowest tier of the network.

56. The apparatus set forth in claim 52, wherein the apparatus is operable such that the at least one child node forwards the third messages to a sensor node in a lower tier.

57. The apparatus set forth in claim 1, wherein the apparatus is operable as at least one of the one or more affiliated children nodes that is an intermediate node on a path between one or more other nodes and the parent node.

58. The apparatus set forth in claim 57, further comprising instructions capable of being used to cause powering-on, at the intermediate node, a receiver to listen for the scheduling message.

59. The apparatus set forth in claim 57, further comprising instructions capable of being used to allow receipt of the scheduling message from the parent node in the network.

60. The apparatus set forth in claim 59, wherein the scheduling message specifies a communication schedule that indicates times at which the intermediate and parent nodes may communicate with one another.

61. The apparatus set forth in claim 59, wherein the scheduling message specifies a communication schedule that indicates times at which the intermediate node may communicate with each of the one or more other nodes.

62. The apparatus set forth in claim 57, further comprising instructions capable of being used to cause organization of the intermediate node, the parent node, and the one or more other nodes in the network into a hierarchy of tiers.

63. The apparatus set forth in claim 57, further comprising instructions capable of being used to cause transmission of data messages to the one or more nodes in a lower tier of the network when a transmitter is powered-on.

64. The apparatus set forth in claim 57, further comprising instructions capable of being used to cause communication of the scheduling message to the parent node in a higher tier of the network when a transmitter is powered-on.

65. The apparatus set forth in claim 1, further comprising instructions capable of being used to allow receipt of third messages from neighboring nodes in a network notifying of the neighboring nodes'"'"' presence in the network.

66. The apparatus set forth in claim 65, further comprising instructions capable of being used to cause determination of a first communication schedule that indicates times for communicating with each of the neighboring nodes and a second communication schedule that indicates times for each of the neighboring nodes to communicate with other nodes in the network.

67. The apparatus set forth in claim 66, further comprising instructions capable of being used to cause communication of the scheduling message to each of the neighboring nodes, wherein the scheduling message includes the first communication schedule and the second communication schedule.

68. The apparatus set forth in claim 1, wherein at least one of the one or more first messages or the second messages includes the scheduling message.

69. The apparatus set forth in claim 1, wherein at least one of the one or more first messages or the second messages includes a data message.

70. The apparatus set forth in claim 1, wherein the instructions capable of being used to cause storage of first data, the instructions capable of being used to cause storage of second data, and the instructions capable of being used to cause message communication are stored in random access memory.

71. The apparatus set forth in claim 1, wherein the instructions capable of being used to cause storage of first data, the instructions capable of being used to cause storage of second data, and the instructions capable of being used to cause message communication are stored in read only memory.

72. The apparatus set forth in claim 1, wherein the instructions capable of being used to cause storage of first data, the instructions capable of being used to cause storage of second data, and the instructions capable of being used to cause message communication are stored in permanent storage.

73. The apparatus set forth in claim 1, wherein the instructions capable of being used to cause storage of first data, the instructions capable of being used to cause storage of second data, and the instructions capable of being used to cause message communication are stored in semi-permanent storage.

74. The apparatus set forth in claim 1, wherein the instructions capable of being used to cause storage of first data, the instructions capable of being used to cause storage of second data, and the instructions capable of being used to cause message communication are stored in temporary storage.

75. The apparatus set forth in claim 1, wherein the instructions capable of being used to cause storage of first data are operable to cause the storage of the first data in response to receipt of a particular message.

76. The apparatus set forth in claim 1, wherein the instructions capable of being used to cause storage of second data are operable to cause the storage of the second data in response to receipt of a particular message.

77. The apparatus set forth in claim 76, wherein the particular message includes an affiliation message.

78. The apparatus set forth in claim 1, wherein the apparatus is operable such that clock drift is counteracted.

79. The apparatus set forth in claim 1, wherein the second data further comprises next-tier information.

80. The apparatus set forth in claim 79, wherein the next-tier information includes times at which at least one of the one or more affiliated children nodes transmit third messages to, or receive fourth messages from, their affiliated children.

81. The apparatus set forth in claim 1, further comprising instructions capable of being used to cause identification of link quality.

82. The apparatus set forth in claim 81, wherein the link quality is identified based on a signal strength.

83. The apparatus set forth in claim 81, wherein the link quality is identified based on an error rate.

84. The apparatus set forth in claim 81, further comprising instructions capable of being used to cause selection of a particular node based on the identified link quality.

85. The apparatus set forth in claim 1, wherein the second data is generated based on a number of the affiliated children nodes.

86. The apparatus set forth in claim 1, wherein the first data and the second data are components of a same data structure encoded on the device-readable medium.

87. The apparatus set forth in claim 1, wherein the first time schedule is for only communicating the one or more first messages from the parent node to the at least one of the one or more affiliated children nodes.

88. The apparatus set forth in claim 1, wherein the second time schedule is for only communicating the one or more second messages to the parent node from the at least one of the one or more affiliated children nodes.

89. The apparatus set forth in claim 1, wherein the first time schedule and the second time schedule are components of a same data structure encoded on the device-readable medium.

90. The apparatus set forth in claim 1, wherein the instructions capable of being used to cause storage of first data and the instructions capable of being used to cause storage of second data, are stored on the apparatus which is operable to function as the parent node.

91. The apparatus set forth in claim 1, wherein the instructions capable of being used to cause storage of first data and the instructions capable of being used to cause storage of second data, are stored on the apparatus which is operable to function as one of the one or more affiliated children nodes.

92. The apparatus set forth in claim 1, wherein the second time schedule is for receiving the one or more second messages at the parent node from each of the one or more affiliated children nodes.

93. The apparatus set forth in claim 1, further comprising instructions capable of being used to cause utilization of the scheduling message.

94. The apparatus set forth in claim 93, further comprising instructions capable of being used to cause powering-on a receiver to listen for the scheduling message.

95. The apparatus set forth in claim 1, wherein the apparatus is operable to communicate with other nodes in a public land mobile network.

96. The apparatus set forth in claim 1, wherein the apparatus is operable to communicate with other nodes in a public switched telephone network.

97. The apparatus set forth in claim 1, wherein the apparatus is operable to communicate with other nodes in a metropolitan area network.

98. The apparatus set forth in claim 1, wherein the apparatus is operable to communicate with other nodes in a local area network.

99. The apparatus set forth in claim 1, wherein the apparatus is operable to communicate with other nodes in a general packet radio service network.

100. The apparatus set forth in claim 1, wherein the apparatus is operable to communicate with other nodes in a cellular digital packet data network.

101. The apparatus set forth in claim 1, wherein the apparatus is operable such that at least a portion of the second data is generated by the parent node.

102. The apparatus set forth in claim 1, wherein the apparatus is operable such that at least a portion of the second data is generated by one of the one or more affiliated children nodes.

103. The apparatus set forth in claim 1, wherein the apparatus is operable such that the first time schedule of the second data is allocated by the parent node.

104. The apparatus set forth in claim 1, wherein the apparatus is operable such that at least one aspect of a communication schedule is allocated by one of the one or more affiliated children nodes.

105. The apparatus set forth in claim 1, wherein the apparatus is operable such that the second time schedule of the second data is allocated by the parent node.

106. The apparatus set forth in claim 1, wherein the apparatus is operable such that at least a portion of the second data includes a derived schedule.

107. The apparatus set forth in claim 1, wherein the apparatus is capable of operating as a parent node.

108. The apparatus set forth in claim 1, wherein the apparatus is capable of operating as a child node of the one or more children nodes.

109. The apparatus set forth in claim 108, wherein the child node includes a timer for dictating when a receiver of the child node is turned off.

110. The apparatus set forth in claim 108, wherein the child node includes a timer for dictating a maximum time when a receiver of the child node is turned off.

111. The apparatus set forth in claim 1, wherein the sleep includes a powering off operation.

112. The apparatus set forth in claim 1, wherein the communication of the scheduling message includes receiving the scheduling message.

113. The apparatus set forth in claim 1, wherein the communication of the scheduling message includes transmitting the scheduling message.

114. The apparatus set forth in claim 1, wherein the scheduling message is communicated by being transmitted from the parent node to at least one of the one or more affiliated children nodes.

115. The apparatus set forth in claim 1, wherein the scheduling message includes the first data.

116. The apparatus set forth in claim 1, wherein the scheduling message includes the second data.

117. The apparatus set forth in claim 1, wherein the apparatus is operable to cause at least one of the one or more affiliated children nodes to sleep.

118. The apparatus set forth in claim 1, wherein the child/parent time slots include child-to-parent time slots.

119. The apparatus set forth in claim 1, wherein the child/parent time slots include parent-to-child time slots.

120. The apparatus set forth in claim 1, wherein the apparatus is configured such that the manner of the message communication is caused for power saving purposes by allowing at least one of the one or more affiliated children nodes to sleep, utilizing both the first data and the second data.

121. The apparatus set forth in claim 1, wherein the first time schedule is for transmitting the one or more first messages from the parent node to more than one of the affiliated children nodes and the second time schedule is for receiving the one or more second messages at the parent node from more than one of the affiliated children nodes.

122. The apparatus set forth in claim 1, wherein a first one of the child/parent time slots associated with a first one of the affiliated children nodes and a second one of the child/parent time slots associated with a second one of the affiliated children nodes are temporally adjacent, with at least one signal therebetween.

123. The apparatus set forth in claim 122, wherein the at least one signal is associated with a slot for other data.

124. The apparatus set forth in claim 122, wherein the at least one signal includes data associated with a third one of the child/parent time slots associated with a third one of the affiliated children nodes.

125. The apparatus set forth in claim 1, wherein the apparatus is operable such that the scheduling message includes both the first data and the second data.

126. The apparatus set forth in claim 1, wherein the apparatus is configured such that the plurality of child/parent time slots associated with the different ones of the affiliated children nodes are temporally contiguous.

127. The apparatus set forth in claim 1, wherein the allowing at least one of the one or more affiliated children nodes to sleep includes causing at least one of the one or more affiliated children nodes to sleep.

128. The apparatus set forth in claim 1, further comprising instructions capable of being used to cause storage of fourth data comprising a time schedule allocating times for a plurality of the affiliated children nodes.

129. The apparatus set forth in claim 1, wherein the apparatus is operable to communicate with other nodes in a cellular network.

130. The apparatus set forth in claim 1, wherein the one or more identifiers associated with the one or more children nodes include one or more unique identifiers.

131. The apparatus set forth in claim 1, wherein the identifier associated with the parent node includes a unique identifier.

132. The apparatus set forth in claim 1, wherein the one or more identifiers associated with the one or more children nodes include one or more identifiers of the one or more children nodes.

133. The apparatus set forth in claim 1, wherein the identifier associated with the parent node includes an identifier of the parent node.

134. The apparatus set forth in claim 1, wherein the one or more identifiers associated with the one or more children nodes are unique to the one or more children nodes.

135. The apparatus set forth in claim 1, wherein the identifier associated with the parent node is unique to the parent node.

136. The apparatus set forth in claim 1, wherein at least one of the first time schedule or the second time schedule indicates a time.

137. The apparatus set forth in claim 1, wherein at least one of the first time schedule or the second time schedule indicates a time period.

138. The apparatus set forth in claim 1, wherein at least one of the first time schedule or the second time schedule indicates a maximum time period.

139. The apparatus set forth in claim 1, wherein at least one of the first time schedule or the second time schedule indicates a time to start the message communication.

140. The apparatus set forth in claim 1, wherein at least one of the first time schedule or the second time schedule indicates a time to power-off a component of the apparatus.

141. The apparatus set forth in claim 1, wherein the instructions include computer code.

142. The apparatus set forth in claim 1, wherein the apparatus is operable such that the second data includes first schedule data received by the apparatus from at least one other node and second schedule data generated by the apparatus.

143. The apparatus set forth in claim 1, wherein at least one of the first time schedule or the second time schedule indicates a time to operate a component of the apparatus.

144. The apparatus set forth in claim 1, wherein at least one of the first time schedule or the second time schedule indicates a time to power-on a component of the apparatus.

145. An apparatus with a non-transitory device-readable medium, comprising:

instructions capable of being used to cause storage of first data comprising identifiers of children nodes affiliated with a parent node in a network, wherein the apparatus is operable such that at least one of the affiliated children nodes is capable of serving as an intermediate node on a path between one or more other nodes and the parent node;

instructions capable of being used to cause storage of second data comprising a first time schedule for communication of first messages from the parent node to one or more of the affiliated children nodes and a second time schedule for communication of second messages to the parent node from one or more of the affiliated children nodes;

instructions capable of being used to cause storage of third data comprising an identifier for the parent node;

instructions capable of being used to cause message communication, the message communication capable of being performed using the first data, the third data, and the second data comprising the first time schedule for communication of the first messages from the parent node to one or more of the affiliated children nodes and the second time schedule for communication of the second messages to the parent node from one or more of the affiliated children nodes;

instructions capable of being used to cause a plurality of child-to-parent time slots associated with different ones of the affiliated children nodes to be temporally grouped together; and

instructions capable of being used to allow receipt of a scheduling message from the parent node in the network, wherein the scheduling message specifies a first communication schedule that indicates times at which the intermediate and parent nodes may communicate with one another, and a second communication schedule that indicates times at which the intermediate node may communicate with each of the one or more other nodes.

146. The apparatus set forth in claim 145, further comprising instructions capable of being used to cause selective powering-on and powering-off of a receiver or a transmitter based on the first or second communication schedules.