Boolean formulation for sensor allocation problem and its efficient solver

ABSTRACT

This paper proposes a sensor allocation technique that can be applied to a sensor network constructed of many sensor nodes having multiple sensors. First, after describing the sensor network model, the problem is formulated. The formulation can handle the following two cases: (1) a minimum number of sensor nodes, and (2) a maximum number of sensor nodes, each of which uses only one or a few of its sensors. The formulation is based on 0-1 Integer Linear Programming. A dedicated solver using a Binary Decision Diagram (BDD) is also described. The proposed method can deal with the sudden death of a sensor and can rapidly reproduce optimal solutions without the dead sensor. According to the experimental results, all optimal and feasible solutions are obtained within 5 seconds in the case of 100 sensors.

REFERENCES

• 1: I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, "A Survey on sensor networks," IEEE Communications Magazine. pp. 102--114, August 2002.
• 2: E. Biagioni, and K. Bridges, "The Application of sensor technology to assist the recovery of rare and endangered species," Special Issue of Distributed Sensor Networks for the International Journal of High Performance Computing Applications, Vol. 16, pp. 315--324, August 2002.
• 3: Crossbow Technology, Inc http://www.xbow.com
• 4: Millennial Net, Inc http://www.millennial.net
• 5: Hitachi Wirelessinfo Venture Company http://www.hitachi.co.jp/wirelessinfo/airsense/
• 6: S. Shakkottai, R. Srikant, and N. Shroff, "Unreliable Sensor Grids: Coverage, Connectivity and Diameter," IEEE Proc. INFOCOM'03, March 2003.
• 7: Sameer Tilak , Nael B. Abu-Ghazaleh , Wendi Heinzelman, Infrastructure tradeoffs for sensor networks, Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570738.570746]
• 8: Song Han , Edward Chan , Reynold Cheng , Kam-Yiu Lam, A Statistics-Based Sensor Selection Scheme for Continuous Probabilistic Queries in Sensor Networks, Proceedings of the 11th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA'05), p.331-336, August 17-19, 2005 [doi>10.1109/RTCSA.2005.15]
• 9: Yuzhen Liu , Weifa Liang, Approximate Coverage in Wireless Sensor Networks, Proceedings of the The IEEE Conference on Local Computer Networks 30th Anniversary, p.68-75, November 15-17, 2005 [doi>10.1109/LCN.2005.32]
• 10: Roger Mailler , Victor Lesser , Bryan Horling, Cooperative negotiation for soft real-time distributed resource allocation, Proceedings of the second international joint conference on Autonomous agents and multiagent systems, July 14-18, 2003, Melbourne, Australia [doi>10.1145/860575.860667]
• 11: Mike Esler , Jeffrey Hightower , Tom Anderson , Gaetano Borriello, Next century challenges: data-centric networking for invisible computing: the Portolano project at the University of Washington, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.256-262, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313553]
• 12: Yannis Kotidis, Snapshot Queries: Towards Data-Centric Sensor Networks, Proceedings of the 21st International Conference on Data Engineering (ICDE'05), p.131-142, April 05-08, 2005 [doi>10.1109/ICDE.2005.134]
• 13: Randal E. Bryant, Graph-based algorithms for Boolean function manipulation, IEEE Transactions on Computers, v.35 n.8, p.677-691, Aug. 1986 [doi>10.1109/TC.1986.1676819]
• 14: R. Ebendt, G. Fey, and R. Frechsler, Advanced BDD Optimization, Springer, 2005.
• 15: A. Srinivasan, T. Kam, S. Malik, and R. E. Brayton, "Algorithm for Discrete Function Manipulation," IEEE Proc. ICCAD'90, pp. 92--95, November 1990.
• 16: B. Lin and F. Somenzi, "Minimization of Symbolic Relations," IEEE Proc. ICCAD'90, pp. 88--91, November 1990.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization

General Terms:
Algorithms

Keywords:
BDD, combinational optimization, dynamic allocation