Information-directed routing in ad hoc sensor networks

ABSTRACT

In a sensor network, data routing is tightly coupled to the needs of a sensing task, and hence the application semantics. This paper introduces the novel idea of information-directed routing, in which routing is formulated as a joint optimization of data transport and information aggregation. The routing objective is to minimize communication cost while maximizing information gain, differing from routing considerations for more general ad hoc networks. The paper uses the concrete problem of locating and tracking possibly moving signal sources as an example of information generation processes, and considers two common information extraction patterns in a sensor network: routing a user query from an arbitrary entry node to the vicinity of signal sources and back, or to a prespecified exit node, maximizing information accumulated along the path. We derive information constraints from realistic signal models, and present several routing algorithms that find near-optimal solutions for the joint optimization problem. Simulation results have demonstrated that information-directed routing is a significant improvement over a previously reported greedy algorithm, as measured by sensing quality such as localization and tracking accuracy and communication quality such as success rate in routing around sensor holes.

REFERENCES

• 1: F. Zhao, J. Shin, and J. Reich, "Information-driven dynamic sensor collaboration," IEEE Signal Processing Magazine, vol. 19, pp. 61--72, Mar. 2002.
• 2: R. Brooks, C. Griffin, and D. Friedlander, "Self-organized distributed sensor network entity tracking," International Journal of High-Performance Computing Applications, vol. 16, no. 3, 2002.
• 3: J. Liu, J. E. Reich, and F. Zhao, "Collaborative in-network processing for target tracking," EURASIP, Journal on Applied Signal Processing, vol. 2003, pp. 378--391, Mar. 2003.
• 4: T. Clausen, G. Hansen, L. Christensen, and G. Behrmann, "The optimized link state routing protocol, evaluation through experiments and simulation," in IEEE Symposium on Wireless Personal Mobile Communication, 2001.
• 5: Charles E. Perkins , Pravin Bhagwat, Highly dynamic Destination-Sequenced Distance-Vector routing (DSDV) for mobile computers, ACM SIGCOMM Computer Communication Review, v.24 n.4, p.234-244, Oct. 1994
• 6: Charles E. Perkins , Elizabeth M. Royer, Ad-hoc On-Demand Distance Vector Routing, Proceedings of the Second IEEE Workshop on Mobile Computer Systems and Applications, p.90, February 25-26, 1999
• 7: 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]
• 8: R. C. Shah and J. M. Rabaey, "Energy aware routing for low energy ad hoc sensor networks," in Proc. IEEE Wireless Communication and Networking Conference, (Orlando, FL), Mar. 2001.
• 9: R. C. Shah and J. M. Rabaey, "Energy aware routing for low energy ad hoc sensor networks," in Proc. IEEE Wireless Communication and Networking Conference, (Orlando, FL), Mar. 2001.
• 10: Young-Bae Ko , Nitin H. Vaidya, Geocasting in Mobile Ad Hoc Networks: Location-Based Multicast Algorithms, Proceedings of the Second IEEE Workshop on Mobile Computer Systems and Applications, p.101, February 25-26, 1999
• 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: M. Chu, H. Haussecker, and F. Zhao, "Scalable information-driven sensor querying and routing for ad hoc heterogeneous sensor networks," International Journal of High-Performance Computing Applications, vol. 16, no. 3, 2002.
• 13: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 14: D. P. Bertsekas, Nonlinear Programming. Belmont, MA: Athena Scientific, 1995.
• 15: Q. Huang, C. Lu, and G.-C. Roman, "Mobicast: Just-in-time multicast for sensor networks under spatiotemporal constraints," in Information Processing in Sensor Networks, Proc. of IPSN 2003, Apr. 2003.
• 16: Richard E. Korf, Real-time heuristic search, Artificial Intelligence, v.42 n.2-3, p.189-211, March 1990 [doi>10.1016/0004-3702(90)90054-4]
• 17: E. J. Cockayne and D. G. Schiller, "Computation of Steiner minimal trees," in Combinatorics (Conference on Combinatorial Mathematics) (D. J. A. Welsh and D. R. Woodall, eds.), (Southend-on-Sea, Essex, England), pp. 53--71, Institute of Math. and its applications, 1972.
• 18: M. Imase and B. M. Waxman, "Dynamic Steiner tree problem," SIAM J. Discrete Math., vol. 4, pp. 369--384, 1991.
• 19: N. Alon and Y. Azar, "On-line Steiner trees in the Euclidean plane," Discrete Comput. Geom., vol. 10, pp. 113--121, 1993.

INDEX TERMS

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

General Terms:
Algorithms

Keywords:
ad hoc network, information, routing, sensor network, target localization