In the protocols designed for wireless sensor networks (WSNs), energy-efficiency is a critical concern because sensor nodes are typically battery powered and expected to survive as long as possible. The end-to-end delay is also crucial to the success of time-sensitive applications, such as, for example, fire alarm and intrusion detection systems, where obsolete data is useless and may even be harmful. Thus, both energy-efficiency and end-to-end delay are important considerations when designing protocols for time-sensitive wireless sensor networks [1] (see Table 1 below for full citation).
Conventional media access control (MAC) protocols with sleep/wake schedules can be roughly categorized into synchronized and asynchronous protocols, according to the schedule pattern. In synchronized protocols [2], [3], nodes in the neighboring area periodically exchange synchronization messages with each other and operate their schedules at the same pace. However, periodic message exchanges incur an additional communications burden, consuming a considerable amount of energy. If sensor nodes are idle most of time, keeping them synchronized is inefficient. In asynchronous protocols, except for the sink, all nodes sleep and wake up independently. Due to the lack of the knowledge regarding each other's schedules, a sender has to wait for a receiver to wake up before transmitting data packets.
In B-MAC [4], a sender precedes the data packet with a preamble that is slightly longer than the sleep interval of a receiver. When a node wakes up and detects the preamble, it waits for the end of the preamble and prepares to receive the subsequent data packet if it is the destination. In X-MAC [5], a sender transmits a series of short preambles separated by intervals, including the address of the receiver, to awaken a target receiver. When the receiver wakes up and receives a preamble, it replies with a message during the interval to notify the sender it is waking up and prepares to receive data packets. In RI-MAC [6], instead of transmitting preambles to awaken the receiver, a sender silently waits for a waking-up notification from a receiver, which occupies less channel time.
In geographic routing, a sender selects a next-hop relay based on the location of the sender, its one-hop neighbors, and the destination. In one conventional system [7], each sender chooses the neighbor that is closest to the destination as the next-hop relay, while the sender in another conventional system [8] prefers the neighbor with the shortest projected distance. Some other recent conventional protocols assign a hop-based coordinate to each node to support online forwarding in the absence of geographic location. In Gradient Landmark-based Distributed Routing (GLIDER) [9] for sensor networks, some nodes are selected as anchor nodes and other nodes maintain a vector of hop count distances to each anchor node. Packets are forwarded to the neighbor that has the minimum Hamming distance to the destination. The efficiency of GLIDER depends on whether a good set of anchor nodes are selected. VCap [10] also assigns virtual coordinates to each node and shows that the performance of online forwarding with the virtual coordinate system is slightly below the performance with physical locations when the node density is high enough. These conventional systems were aimed at finding a global shortest forwarding path, which is also deemed the minimum energy path under the assumption of the unit disk model. However, recent experimental studies [11] have shown that unit disk model is fundamentally impractical and the energy consumed by transmission depends not only on the distance between the sender and receiver, but also on some random environmental factors.
Existing cross-layer solutions also fail to make a good tradeoff between energy-efficiency and delay in asynchronous networks. In an “integrated MAC/Routing protocol” (MACRO) [12], the sender tries different transmitting power levels to seek the next-hop relay with the maximal geographical progress per unit of transmitting power. This search may result in unacceptable end-to-end delays and considerable energy costs, especially in low duty cycle networks where nodes wake up very infrequently. It has been pointed out in [13] that it is not clear whether anycast forwarding will minimize the actual end-to-end delay, which depends on not only the single-hop delay but also the forwarding path. In [13], optimal anycast forwarding and sleep/wake schedule policies are proposed to minimize the end-to-end delay, but the impact of an asynchronous sleep/wake schedule on energy-efficiency is not considered.
In [14], the joint control problem of how to optimally control the sleep/wake schedule, the anycast candidate set of next-hop neighbors, and anycast priorities to maximize the lifetime of event-driven networks subject to a constraint on the expected end-to-end delay was studied. However, the priority matrix of [14] is seldom applicable since the probability that multiple candidates wake up at the same beacon interval is very low, especially in low duty cycle networks.
Recent cross-layer works [13], [14], [15] for event-driven and asynchronous networks have usually assumed that data reports are very rare and small in size. Then, they simply ignore the energy consumed by forwarding packets and mainly consider how to control sleep/wake schedules to make a good tradeoff between the energy consumed by sleep/wake schedules and the forwarding delay. However, packet forwarding may consume considerable energy even in event-driven networks, especially when packets are large in size.
In MAC protocols designed for WSNs, sleep/wake schedules are widely employed to reduce idle listening and energy consumption. In asynchronous sleep/wake schedule protocols [4], [5], [6], each node operates its sleep/wake schedule independently. A non-sender node just periodically wakes up for a short period to check whether another node is preparing to send packet to it. However, a sender is required to stay active and wait for a receiver or receivers to wake up, due to the lack of knowledge regarding the schedule of the receiver or receivers. For event-driven networks, it has been demonstrated that asynchronous schedule protocols consume less energy than synchronized ones. In addition, asynchronous schedule protocols are easier to implement.
Online forwarding techniques may be used to transfer data reports from monitoring nodes to the sink. In online forwarding protocols [10], [15], [16], [17], the forwarding path is selected locally and without using routing tables.
Below is a table of references cited in the Background, all of which are incorporated herein in their entireties by reference.
TABLE 1Bibliography[1] S. Waharte, R. Boutaba, Y. Iraqi, and B. Ishibashi, “Routing protocols in wireless mesh networks:challenges and design considerations,” Multimedia Tools Appl., vol. 29, no. 3, pp. 285-303, 2006.[2] W. Ye, J. Heidemann, and D. Estrin, “An energy efficient mac protocol for wireless sensor networks,” inProc. of the 21st IEEE INFOCOM, 2002.[3] T. van Dam and K. Langendoen, “An adaptive energy efficient mac protocol for wireless sensor networks,”in 1st ACM Conference on Embedded Networked Sensor Systems (SenSys), pages 171-180, 2003.[4] J. Polastre, J. Hill, and D. Culler, “Versatile low power media access for wireless sensor networks,” in Procof the 2nd ACM Conference on Embedded Networked Sensor Systems (SenSys), pages 95-107, November 2004.[5] M. Buettner, G. Yee, E. Anderson and R. Han, “X-MAC: a short preamble MAC protocol for duty-cycledwireless sensor networks,” in Proc. of the 4th ACM Conference on Embedded Sensor Systems (SenSys), 2006,pp. 307-320.[6] Y. Sun, O. Gurewitz, and D. B. Johnson, “RI-MAC: A receiver initiated asynchronous duty cycle MACprotocol for dynamic traffic load,” in Proc of the 6th ACM Conference on Embedded Networked SensorSystems (SenSys), November 2008.[7] B. Karp and H. T. Kung, “GPSR: Greedy perimeter stateless routing for wireless networks,” in Proc. of the6th ACM/IEEE MOBICOM, 2000, pp. 243-254.[8] H. Takagi and L. Kleinrock, “Optimal transmission ranges for randomly distributed packet radio terminals,”IEEE Transactions on Communications, vol. 32, no. 3, pp. 246-257, 1984.[9] Q. Fang, J. Gao, L. Guibas, V. de Silva, and L. Zhang, “GLIDER: Gradient landmark-based distributedrouting for sensor networks,” in Proc. of the 24th IEEE INFOCOM, March 2005.[10] A. Caruso, S. Chessa, S. De, and A. Urpi, “GPS free coordinate assignment and routing in wireless sensornetworks,” in Proc. Of the 24th IEEE INFOCOM, 2005.[11] M. Zuniga and B. Krishnamachari, “Analyzing the transitional region in low power wireless links,” in Proc.of IEEE SECON, 2004.[12] D. Ferrara, et. al., “MACRO: An Integrated MAC/Routing Protocol for Geographical Forwarding inWireless Sensor Networks,” in Proc. of the 24th IEEE INFOCOM, March 2005.[13] J. Kim, X. Lin, and N. B. Shroff, “Optimal anycast technique for delay-sensitive energy-constrainedasynchronous sensor networks,” in Proc. of the 28th IEEE INFOCOM, 2009.[14] J. Kim, X. Lin, N. B. Shroff, and P. Sinha, “On maximizing the lifetime of delay-sensitive wireless sensornetworks with anycast,” in Proc. of the 27th IEEE INFOCOM, 2008.[15] S. Kulkarni, A. Iyer and C. Rosenberg, “An address-light, integrated MAC and routing protocol forwireless sensor networks,” IEEE/ACM Transactions on Networking, vol. 14, no. 4, pp. 793-806, August 2006.[16] P. Casari, M. Nati, C. Petrioli, and M. Zorzi, “Efficient non-planar routing around dead ends in sparsetopologies using random forwarding,” in Proc. of IEEE International Conference on Communications, 2007.[17] I. Stojmenovic and X. Lin, “Power-aware localized routing in wireless network,” IEEE Transactions onParallel and Distributed Systems, vol. 12, no. 11, pp. 1122-1133, November 2001.
USPTO Backgrounds
USPTO Backgrounds