|
ABSTRACT
This paper presents Span, a power saving technique for multi-hop ad hoc wireless networks that reduces energy consumption without significantly diminishing the capacity or connectivity of the network. Span builds on the observation that when a region of a shared-channel wireless network bag a sufficient density of nodes, only a small number of them need be on at any time to forward traffic for active connections.
Span is a distributed, randomized algorithm where nodes make local decisions on whether to sleep, or to join a forwarding backbone as a coordinator. Each node bases its decision on an estimate of how many of its neighbors will benefit from it being awake, and the amount of energy available to it. We give a randomized algorithm where coordinators rotate with time, demonstrating how localized node decisions lead to a connected, capacity-preserving global topology.
Improvement in system lifetime due to Span increases as the ratio of idle-to-sleep energy consumption increases, and increases as the density of the network increases. For example, our simulations show that with a practical energy model, system lifetime of an 802.11 network in power saving mode with Span is a factor of two better than without. Span integrates nicely with 802.11—when run in conjunction with the 802.11 power saving mode, Span improves communication latency, capacity, and system lifetime.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
1
|
Wireless LAN Medium Access Control and Physical Layer Specifications, Aug. 1999. IEEE 802.11 Standard (IEEE Computer Society LAN MAN Standards Committee).
|
| |
2
|
Broch, J., Johnson, D., and Maltz, D. The Dynamic Source Routing Protocol for Mobile Ad Hoc Networks. In Internet draft, IETF Mobile Ad Hoc Networking Working Group (Dec. 1998).
|
 |
3
|
Josh Broch , David A. Maltz , David B. Johnson , Yih-Chun Hu , Jorjeta Jetcheva, A performance comparison of multi-hop wireless ad hoc network routing protocols, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.85-97, October 25-30, 1998, Dallas, Texas, United States
[doi> 10.1145/288235.288256]
|
| |
4
|
Chang, J., and Tassiulas, L. Energy Conserving Routing in Wireless Ad Hoc Networks. In Proceedings of IEEE INFOCOM (Tel Aviv, Israel, 2000).
|
| |
5
|
Chesson, G. XTP/protocol engine design. In Proceedings of the IFIP WG6.1/6.4 Workshop (R. uschlikon, May 1989).
|
| |
6
|
Feeney, L., and Nilsson, M. Investigating the Energy Consumption of a Wireless Network Interface in an Ad Hoc Networking Environment. In Proceedings of IEEE INFOCOM (Anchorage, AK, 2001).
|
| |
7
|
Fenner, W. Internet Group Management Protocol, Version 2, Nov 1997. RFC-2236.
|
| |
8
|
Finn, G. G. Routing and Addressing Problems in Large Metropolitan-scale Internetworks. ISI/RR-87-180, ISI, Mar. 1987.
|
 |
9
|
Sally Floyd , Van Jacobson , Steve McCanne , Ching-Gung Liu , Lixia Zhang, A reliable multicast framework for light-weight sessions and application level framing, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.342-356, August 28-September 01, 1995, Cambridge, Massachusetts, United States
|
| |
10
|
|
 |
11
|
Chalermek Intanagonwiwat , Ramesh Govindan , Deborah Estrin, Directed diffusion: a scalable and robust communication paradigm for sensor networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.56-67, August 06-11, 2000, Boston, Massachusetts, United States
[doi> 10.1145/345910.345920]
|
 |
12
|
|
 |
13
|
|
 |
14
|
Jinyang Li , John Jannotti , Douglas S. J. De Couto , David R. Karger , Robert Morris, A scalable location service for geographic ad hoc routing, Proceedings of the 6th annual international conference on Mobile computing and networking, p.120-130, August 06-11, 2000, Boston, Massachusetts, United States
[doi> 10.1145/345910.345931]
|
| |
15
|
W. Mangione-Smith , P. Ghang , S. Nazareth , P. Lettieri , W. Boring , R. Jain, A low power architecture for wireless multimedia systems: lessons learned from building a power hog, Proceedings of the 1996 international symposium on Low power electronics and design, p.23-28, August 12-14, 1996, Monterey, California, United States
|
| |
16
|
CMU Monarch Extensions to ns. http://www.monarch.cs.cmu.edu/.
|
| |
17
|
ns Notes and Documentation. http://www.isi.edu/vint/nsnam/, 2000.
|
 |
18
|
|
 |
19
|
|
| |
20
|
Ramanathan, R., and Rosales-Hain, R. Topology Control of Multi-hop Wireless Networks Using Transmit Power Adjustment. In Proceedings of IEEE INFOCOM (Tel Aviv, Israel, March 2000).
|
| |
21
|
Rodoplu, V., and Meng, T. H. Minimum Energy Mobile Wireless Networks. In Proceedings of the IEEE International Conference on Communications (ICC) (Atlanta, GA, June 1998), vol. 3, pp. 1633-1639.
|
| |
22
|
Rohl, C., Woesner, H., and Wolisz, A. A Short Look on Power Saving Mechanisms in the Wireless LAN Standard Draft IEEE 802.11. In Proceedings of the the 6th WINLAB Workshop on Third Generation Wireless Systems (New Brunswick, NJ, Mar. 1997).
|
 |
23
|
Timothy J. Shepard, A channel access scheme for large dense packet radio networks, Conference proceedings on Applications, technologies, architectures, and protocols for computer communications, p.219-230, August 28-30, 1996, Palo Alto, California, United States
|
 |
24
|
Suresh Singh , Mike Woo , C. S. Raghavendra, Power-aware routing in mobile ad hoc networks, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.181-190, October 25-30, 1998, Dallas, Texas, United States
[doi> 10.1145/288235.288286]
|
| |
25
|
Stemm, M., and Katz, R. Reducing Power Consumption of Network Interfaces in Hand-held Devices. In Proceedings of the Third Workshop on Mobile Multimedia Communications (MoMuC-3) (Princeton, NJ, 1996).
|
| |
26
|
Wattenhofer, R., Li, L., Bahl, P., and Wang, Y.-M. Distributed Topology Control for Power Efficient Operation in Multihop Wireless Ad Hoc Networks. In Proceedings of IEEE INFOCOM (Anchorage, AK, 2001).
|
| |
27
|
Xu, Y., Heidemann, J., and Estrin, D. Adaptive Energy-Conserving Routing for Multihop Ad Hoc Networks. Tech. Rep. 527, USC/ISI, Oct. 2000.
|
 |
28
|
|
CITED BY 211
|
|
|
|
|
|
|
|
Alan Mainwaring , David Culler , Joseph Polastre , Robert Szewczyk , John Anderson, Wireless sensor networks for habitat monitoring, Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, September 28-28, 2002, Atlanta, Georgia, USA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Phillip Stanley-Marbell , Diana Marculescu , Radu Marculescu , Pradeep K. Khosla, Modeling, Analysis, and Self-Management of Electronic Textiles, IEEE Transactions on Computers, v.52 n.8, p.996-1010, August 2003
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Pierpaolo Bergamo , Alessandra Giovanardi , Andrea Travasoni , Daniela Maniezzo , Gianluca Mazzini , Michele Zorzi, Distributed power control for energy efficient routing in ad hoc networks, Wireless Networks, v.10 n.1, p.29-42, January 2004
|
|
|
|
|
|
W. Steven Conner , Jasmeet Chhabra , Mark Yarvis , Lakshman Krishnamurthy, Experimental evaluation of synchronization and topology control for in-building sensor network applications, Proceedings of the 2nd ACM international conference on Wireless sensor networks and applications, September 19-19, 2003, San Diego, CA, USA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Jianping Pan , Y. Thomas Hou , Lin Cai , Yi Shi , Sherman X. Shen, Topology control for wireless sensor networks, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA
|
|
|
|
|
|
Maruti Gupta , Suresh Singh, Greening of the internet, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany
|
|
|
Aman Kansal , Arun A. Somasundara , David D. Jea , Mani B. Srivastava , Deborah Estrin, Intelligent fluid infrastructure for embedded networks, Proceedings of the 2nd international conference on Mobile systems, applications, and services, June 06-09, 2004, Boston, MA, USA
|
|
|
|
|
|
|
|
|
Tian He , Sudha Krishnamurthy , John A. Stankovic , Tarek Abdelzaher , Liqian Luo , Radu Stoleru , Ting Yan , Lin Gu , Jonathan Hui , Bruce Krogh, Energy-efficient surveillance system using wireless sensor networks, Proceedings of the 2nd international conference on Mobile systems, applications, and services, June 06-09, 2004, Boston, MA, USA
|
|
|
|
|
|
|
|
|
Gang Zhou , Tian He , Sudha Krishnamurthy , John A. Stankovic, Impact of radio irregularity on wireless sensor networks, Proceedings of the 2nd international conference on Mobile systems, applications, and services, June 06-09, 2004, Boston, MA, USA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Deepak Ganesan , Alberto Cerpa , Wei Ye , Yan Yu , Jerry Zhao , Deborah Estrin, Networking issues in wireless sensor networks, Journal of Parallel and Distributed Computing, v.64 n.7, p.799-814, July 2004
|
|
|
|
|
|
Xiaorui Wang , Guoliang Xing , Yuanfang Zhang , Chenyang Lu , Robert Pless , Christopher Gill, Integrated coverage and connectivity configuration in wireless sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Joseph Polastre , Robert Szewczyk , Alan Mainwaring , David Culler , John Anderson, Analysis of wireless sensor networks for habitat monitoring, Wireless sensor networks, Kluwer Academic Publishers, Norwell, MA, 2004
|
|
|
Himanshu Gupta , Vishnu Navda , Samir R. Das , Vishal Chowdhary, Efficient gathering of correlated data in sensor networks, Proceedings of the 6th ACM international symposium on Mobile ad hoc networking and computing, May 25-27, 2005, Urbana-Champaign, IL, USA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Brian Blum , Prashant Nagaraddi , Anthony Wood , Tarek Abdelzaher , Sang Son , Jack Stankovic, An entity maintenance and connection service for sensor networks, Proceedings of the 1st international conference on Mobile systems, applications and services, p.201-214, May 05-08, 2003, San Francisco, California
|
|
|
|
|
|
|
|
|
Joseph Polastre , Jonathan Hui , Philip Levis , Jerry Zhao , David Culler , Scott Shenker , Ion Stoica, A unifying link abstraction for wireless sensor networks, Proceedings of the 3rd international conference on Embedded networked sensor systems, November 02-04, 2005, San Diego, California, USA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Guoliang Xing , Chenyang Lu , Ying Zhang , Qingfeng Huang , Robert Pless, Minimum power configuration in wireless sensor networks, Proceedings of the 6th ACM international symposium on Mobile ad hoc networking and computing, May 25-27, 2005, Urbana-Champaign, IL, USA
|
|
|
Han Namgoong , Dongman Lee , Dukyun Nam, Energy efficient topology for wireless microsensor networks, Proceedings of the 2nd ACM international workshop on Performance evaluation of wireless ad hoc, sensor, and ubiquitous networks, October 10-13, 2005, Montreal, Quebec, Canada
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Sofie Pollin , Bruno Bougard , Rahul Mangharam , Francky Catthoor , Ingrid Moerman , Ragunathan Rajkumar , Liesbet Van der Perre, Optimizing transmission and shutdown for energy-efficient real-time packet scheduling in clustered ad hoc networks, EURASIP Journal on Wireless Communications and Networking, v.5 n.5, p.698-711, October 2005
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Yan Jin , Ju-Yeon Jo , Ling Wang , Yoohwan Kim , Xiaozong Yang, ECCRA: An energy-efficient coverage and connectivity preserving routing algorithm under border effects in wireless sensor networks, Computer Communications, v.31 n.10, p.2398-2407, June, 2008
|
|
|
|
|
|
|
|
|
Sangeeta Bhattacharya , Guoliang Xing , Chenyang Lu , Gruia-Catalin Roman , Octav Chipara , Brandon Harris, Dynamic wake-up and topology maintenance protocols with spatiotemporal guarantees, Proceedings of the 4th international symposium on Information processing in sensor networks, April 24-27, 2005, Los Angeles, California
|
|
|
|
|
|
|
|
|
Erwan Le Merrer , Vincent Gramoli , Anne-Marie Kermarrec , Aline C. Viana , Marin Bertier, Energy aware self-organizing density management in wireless sensor networks, Proceedings of the 1st international workshop on Decentralized resource sharing in mobile computing and networking, July 25-25, 2006, Los Angeles, California
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
H. Jun , W. Zhao , M. H. Ammar , E. W. Zegura , C. Lee, Trading latency for energy in densely deployed wireless ad hoc networks using message ferrying, Ad Hoc Networks, v.5 n.4, p.444-461, May, 2007
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Tian He , Sudha Krishnamurthy , Liqian Luo , Ting Yan , Lin Gu , Radu Stoleru , Gang Zhou , Qing Cao , Pascal Vicaire , John A. Stankovic , Tarek F. Abdelzaher , Jonathan Hui , Bruce Krogh, VigilNet: An integrated sensor network system for energy-efficient surveillance, ACM Transactions on Sensor Networks (TOSN), v.2 n.1, p.1-38, February 2006
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Philip Levis , Sam Madden , David Gay , Joseph Polastre , Robert Szewczyk , Alec Woo , Eric Brewer , David Culler, The emergence of networking abstractions and techniques in TinyOS, Proceedings of the 1st conference on Symposium on Networked Systems Design and Implementation, p.1-1, March 29-31, 2004, San Francisco, California
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Hyewon Jun , Mostafa H. Ammar , Mark D. Corner , Ellen W. Zegura, Hierarchical power management in disruption tolerant networks with traffic-aware optimization, Proceedings of the 2006 SIGCOMM workshop on Challenged networks, p.245-252, September 11-15, 2006, Pisa, Italy
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Ahmed Sobeih , Wei-Peng Chen , Jennifer C. Hou , Lu-Chuan Kung , Ning Li , Hyuk Lim , Hung-Ying Tyan , Honghai Zhang, J-Sim: A Simulation Environment for Wireless Sensor Networks, Proceedings of the 38th annual Symposium on Simulation, p.175-187, April 04-06, 2005
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Kentaro Yanagihara , Jumpei Taketsugu , Kiyoshi Fukui , Shigeru Fukunaga , Shinsuke Hara , Ken-Ichi Kitayama, EACLE: Energy-Aware Clustering Scheme with Transmission Power Control for Sensor Networks, Wireless Personal Communications: An International Journal, v.40 n.3, p.401-415, February 2007
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Pascal Vicaire , Tian He , Qing Cao , Ting Yan , Gang Zhou , Lin Gu , Liqian Luo , Radu Stoleru , John A. Stankovic , Tarek F. Abdelzaher, Achieving long-term surveillance in VigilNet, ACM Transactions on Sensor Networks (TOSN), v.5 n.1, p.1-39, February 2009
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Xiang-Yang Li , YanWei Wu , Ping Xu , GuiHai Chen , Mo Li, Hidden information and actions in multi-hop wireless ad hoc networks, Proceedings of the 9th ACM international symposium on Mobile ad hoc networking and computing, May 26-30, 2008, Hong Kong, Hong Kong, China
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Vrinda Gupta , Rajoo Pandey, Data fusion and topology control in wireless sensor networks, Proceedings of the 5th conference on Applied electromagnetics, wireless and optical communications, p.135-140, December 14-16, 2007, Tenerife, Canary Islands, Spain
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Jinsong Zhang , Malaka Walpola , David Roelant , Hao Zhu , Kang Yen, Self-organization of unattended wireless acoustic sensor networks for ground target tracking, Pervasive and Mobile Computing, v.5 n.2, p.148-164, April, 2009
|
|
|
Jian Chen , Jie Jia , Yingyou Wen , Dazhe Zhao , Jiren Liu, Modeling and extending lifetime of wireless sensor networks using genetic algorithm, Proceedings of the first ACM/SIGEVO Summit on Genetic and Evolutionary Computation, June 12-14, 2009, Shanghai, China
|
|
|
|
|
|
Jie Jia , Jian Chen , Guiran Chang , Yingyou Wen , Jingping Song, Multi-objective optimization for coverage control in wireless sensor network with adjustable sensing radius, Computers & Mathematics with Applications, v.57 n.11-12, p.1767-1775, June, 2009
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Yang Xiao , Yanping Zhang , Miao Peng , Hui Chen , Xiaojiang Du , Bo Sun , Kui Wu, Two and three-dimensional intrusion object detection under randomized scheduling algorithms in sensor networks, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.53 n.14, p.2458-2475, September, 2009
|
|
|
Farshad Ahdi , Vikram Srinivasan , Kee-Chaing Chua, TC-DSA: topology control for delay sensitive applications in wireless sensor networks, The Fourth International Conference on Heterogeneous Networking for Quality, Reliability, Security and Robustness & Workshops, August 14-17, 2007, Vancouver, Canada
|
|
|
|
|
|
Yong Xi , M. Chuah , K. Chang, Performance evaluation of a power management scheme for disruption tolerant network, The Fourth International Conference on Heterogeneous Networking for Quality, Reliability, Security and Robustness & Workshops, August 14-17, 2007, Vancouver, Canada
|
|
|
|
|
|
|
|