Utility based sensor selection

ABSTRACT

Sensor networks consist of many small sensing devices that monitor an environment and communicate using wireless links. The lifetime of these networks is severely curtailed by the limited battery power of the sensors. One line of research in sensor network lifetime management has examined sensor selection techniques, in which applications judiciously choose which sensors' data should be retrieved and are worth the expended energy. In the past, many ad-hoc approaches for sensor selection have been proposed. In this paper, we argue that sensor selection should be based upon a tradeoff between application-perceived benefit and energy consumption of the selected sensor set.We propose a framework wherein the application can specify the utility of measuring data (nearly) concurrently at each set of sensors. he goal is then to select a sequence of sets to measure whose total utility is maximized, while not exceeding the available energy. Alternatively, we may look for the most cost-effective sensor set, maximizing the product of utility and system lifetime.This approach is very generic, and permits us to model many applications of sensor networks. We proceed to study two important classes of utility functions: submodular and supermodular functions. We show that the optimum solution for submodular functions can be found in polynomial time, while optimizing the costeffectiveness of supermodular functions is NP-hard. For a practically important subclass of supermodular functions, we present an LP-based solution if nodes can send for different amounts of time, and show that we can achieve an O(logn) approximation ratio if each node has to send for the same amount of time.Finally, we study scenarios in which the quality of measurements is naturally expressed in terms of distances from targets. We show that the utility-based approach is analogous to a penalty-based approach in those scenarios, and present preliminary results on some practically important special cases.

REFERENCES

• 1: Qunfeng Dong, Maximizing system lifetime in wireless sensor networks, Proceedings of the 4th international symposium on Information processing in sensor networks, April 24-27, 2005, Los Angeles, California
• 2: C. Schurgers and M. B. Srivastava, "Energy efficient routing in wireless sensor networks," in MILCOM, Vienna, VA, 2001, pp. 357--361.
• 3: Qun Li , Javed Aslam , Daniela Rus, Online power-aware routing in wireless Ad-hoc networks, Proceedings of the 7th annual international conference on Mobile computing and networking, p.97-107, July 2001, Rome, Italy [doi>10.1145/381677.381687]
• 4: Jae-Hwan Chang , Leandros Tassiulas, Fast Approximate Algorithms for Maximum Lifetime Routing in Wireless Ad-hoc Networks, Proceedings of the IFIP-TC6 / European Commission International Conference on Broadband Communications, High Performance Networking, and Performance of Communication Networks, p.702-713, May 14-19, 2000
• 5: G. Xing, X. Wang, Y. Zhang, C. Lu, R. Pless, and C. Gill, "Integrated coverage and connectivity configuration for energy conservation in sensor networks," 2005.
• 6: Curt Schurgers , Vlasios Tsiatsis , Saurabh Ganeriwal , Mani Srivastava, Topology management for sensor networks: exploiting latency and density, Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, June 09-11, 2002, Lausanne, Switzerland [doi>10.1145/513800.513817]
• 7: I. Kang and R. Poovendran, "Maximizing static network lifetime of wireless broadcast adhoc networks," in IEEE ICC, Anchorage, Alaska, 2003.
• 8: N. Ehsan and M. Liu, "Minimizing power consumption in sensor networks with quality of service requirement," in to appear in Annual Allerton Confercence on Communications, Control and Computing (Allerton 2005), Allerton, IL, 2005.
• 9: John Byers , Gabriel Nasser, Utility-Based Decision-Making in Wireless Sensor Networks, Boston University, Boston, MA, 2000
• 10: "The Extensible Sensing System." {Online}. Available: http://www.cens.ucla.edu/eoster/ess/
• 11: Robert Szewczyk , Alan Mainwaring , Joseph Polastre , John Anderson , David Culler, An analysis of a large scale habitat monitoring application, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031521]
• 12: Robert Szewczyk , Eric Osterweil , Joseph Polastre , Michael Hamilton , Alan Mainwaring , Deborah Estrin, Habitat monitoring with sensor networks, Communications of the ACM, v.47 n.6, June 2004 [doi>10.1145/990680.990704]
• 13: Anish Arora , Rajiv Ramnath , Emre Ertin , Prasun Sinha , Sandip Bapat , Vinayak Naik , Vinod Kulathumani , Hongwei Zhang , Hui Cao , Mukundan Sridharan , Santosh Kumar , Nick Seddon , Chris Anderson , Ted Herman , Nishank Trivedi , Chen Zhang , Mikhail Nesterenko , Romil Shah , Sandeep Kulkarni , Mahesh Aramugam , Limin Wang , Mohamed Gouda , Young-ri Choi , David Culler , Prabal Dutta , Cory Sharp , Gilman Tolle , Mike Grimmer , Bill Ferriera , Ken Parker, ExScal: Elements of an Extreme Scale Wireless Sensor Network, Proceedings of the 11th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA'05), p.102-108, August 17-19, 2005 [doi>10.1109/RTCSA.2005.47]
• 14: R. Govindan, E. K. D. Estrin, F. Bian, K. Chintalapudi, O. Gnawali, S. Rangwala, R. Gummadi, and T. Stathopoulos,"Tenet: An Architecture for Tiered Embedded Networks," Tech. Rep., November 10 2005.
• 15: J. Paek, K. Chintalapudi, J. Cafferey, R. Govindan, and S. Masri, "A wireless sensor network for structural health monitoring: Performance and experience," in Proceedings of the Second IEEE Workshop on Embedded Networked Sensors (EmNetS-II), Syndney, Australia, May 2005.
• 16: Adrian Vetta, Nash Equilibria in Competitive Societies, with Applications to Facility Location, Traffic Routing and Auctions, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.416, November 16-19, 2002
• 17: U. Feige, G. Kortsarz, and D. Peleg, "The dense k-subgraph problem," in Proc. 25th ACM Symp. on Theory of Computing, 1993.
• 18: U. Feige , M. Seltser, On the densest k-subgraph problems, Weizmann Science Press of Israel, Jerusalem, Israel, 1997
• 19: C. Papadimitriou, "Worst-case and probabilistic analysis of a geometric location problem," SIAM Journal on Computing, vol. 10, pp. 542--557, 1981.
• 20: Tomás Feder , Daniel Greene, Optimal algorithms for approximate clustering, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.434-444, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62255]
• 21: Sanjeev Arora , Prabhakar Raghavan , Satish Rao, Approximation schemes for Euclidean k-medians and related problems, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.106-113, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276718]
• 22: Joseph Polastre , Jason Hill , David Culler, Versatile low power media access for wireless sensor networks, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031508]
• 23: Tijs van Dam , Koen Langendoen, An adaptive energy-efficient MAC protocol for wireless sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958512]
• 24: W. Ye, J. Heidemann, and D. Estrin, "An energy-efficient mac protocol for wireless sensor networks," in Proceedings of the IEEE Infocom, June 2002.
• 25: Chih-fan Hsin , Mingyan Liu, Network coverage using low duty-cycled sensors: random & coordinated sleep algorithms, Proceedings of the third international symposium on Information processing in sensor networks, April 26-27, 2004, Berkeley, California, USA [doi>10.1145/984622.984685]
• 26: 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
• 27: A. Cerpa and D. Estrin, "ASCENT: Adaptive self-configuring sensor networks topologies," in Proceedings of the IEEE Infocom. New York, USA: IEEE, June 2002.
• 28: Benjie Chen , Kyle Jamieson , Hari Balakrishnan , Robert Morris, Span: An energy-efficient coordination algorithm for topology maintenance in Ad Hoc wireless networks, Proceedings of the 7th annual international conference on Mobile computing and networking, p.85-96, July 2001, Rome, Italy [doi>10.1145/381677.381686]
• 29: Ya Xu , John Heidemann , Deborah Estrin, Geography-informed energy conservation for Ad Hoc routing, Proceedings of the 7th annual international conference on Mobile computing and networking, p.70-84, July 2001, Rome, Italy [doi>10.1145/381677.381685]
• 30: S. Shenker, "Fundamental design issues for the future internet," September 1995.
• 31: F. Kelly, A. Maulloo, and D. Tan, "Rate control in communication networks: shadow prices, proportional fairness and stability," in Journal of the Operational Research Society, vol. 49, 1998. {Online}. Available: citeseer.csail.mit.edu/kelly98rate.html
• 32: Volkan Isler , Ruzena Bajcsy, The sensor selection problem for bounded uncertainty sensing models, Proceedings of the 4th international symposium on Information processing in sensor networks, April 24-27, 2005, Los Angeles, California
• 33: G. Mainland, D. C. Parkes, and M. Welsh, "Decentralized, adaptive resource allocation for sensor networks," in In Proceedings of the 2nd USENIX/ACM Symposium on Networked Systems Design and Implementation (NSDI), 2005.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems

General Terms:
Algorithms, Theory

Keywords:
complexity, sensor networks, sensor selection, sub-modular, super-modular, utility