Multi-training sensor networks with bipartite conflict graphs

ABSTRACT

Due to their potential applications in various situations such as battlefield communications, emergency relief, environmental monitoring, and other special-purpose operations, wireless sensor networks have recently emerged as a new and exciting research area that has attracted a good deal of well-deserved attention in the literature. In this work we take the view that a sensor network consists of a set of tiny sensors, massively deployed over a geographical area. The sensors are capable of performing processing, sensing and communicating with each other by radio links. Alongside, with the tiny sensors, more powerful devices referred as Aggregating and Forwarding Nodes, (AFN, for short) are also deployed. In support of their mission, the AFNs are endowed with a special radio interface for long distance communications, miniaturized GPS, and appropriate networking tools for data collection and aggregation. As a fundamental prerequisite for self-organization, the sensors need to acquire some form of location awareness. Since fine-grain location awareness usually assumes that the sensors are GPS-enabled, in the case of tiny sensors the best we can hope for is to endow them with coarse-grain location awareness. This task is referred to as training and its responsibility lies with the AFNs. However, due to the random deployment, some of the sensors fall under the coverage area of several AFNs, in which case the goal is for these sensors to acquire location information relative to all the covering AFNs. The corresponding task is referred to as multi-training.The main contribution of this work is to show that in case the conflict graphs of the AFN coverage is bipartite, multi-training can be completed very fast by a simple algorithm.

REFERENCES

• 1: I. F. Akyildiz , W. Su , Y. Sankarasubramaniam , E. Cayirci, Wireless sensor networks: a survey, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.38 n.4, p.393-422, 15 March 2002 [doi>10.1016/S1389-1286(01)00302-4]
• 2: N. Bulusu, J. Heidemann, and D. Estrin, GP-less low cost outdoor localization for very small devices, IEEE Personal Communications, 7(5): 28--34, 2000.
• 3: David Culler , Deborah Estrin , Mani Srivastava, Guest Editors' Introduction: Overview of Sensor Networks, Computer, v.37 n.8, p.41-49, August 2004 [doi>10.1109/MC.2004.93]
• 4: David E. Culler , Wei Hong, Introduction, Communications of the ACM, v.47 n.6, June 2004 [doi>10.1145/990680.990703]
• 5: Kirk Martinez , Jane K. Hart , Royan Ong, Environmental Sensor Networks, Computer, v.37 n.8, p.50-56, August 2004 [doi>10.1109/MC.2004.91]
• 6: R. Ishak, S. Olariu, S. Salleh and Q. Xu, Dual-training for Massively- Deployed Sensor Networks, 13th International Conference of Telecommunications, Portugal, May 2006.
• 7: Holger Karl , Andreas Willig, Protocols and Architectures for Wireless Sensor Networks, John Wiley & Sons, 2005
• 8: S. Olariu, Q. Xu, A. Wadaa and I. Stojmonovic, A virtual infrastructure for wireless sensor networks, in I. Stojmenivc, Ed., Handbook of Sensor Networks, Wiley 2005, 107--140.
• 9: S. Olariu, A. Wadaa, L. Wilson and M. Eltoweissy, Wireless sensor networks: leveraging the virtual infrastructure, IEEE Network, 18(4), 204, 51--56.
• 10: Stephan Olariu , Mohamed Eltoweissy , Mohamed Younis, ANSWER: autonomous wireless sensor network, Proceedings of the 1st ACM international workshop on Quality of service & security in wireless and mobile networks, October 13-13, 2005, Montreal, Quebec, Canada [doi>10.1145/1089761.1089776]
• 11: K. Sohrabi, J. Gao, V. Ailawadhi, and G. Pottie, Protocols for self-organization of a wireless sensor network, IEEE Personal Communications, October 2000, 16--27.
• 12: A. Wadaa , S. Olariu , L. Wilson , M. Eltoweissy , K. Jones, Training a wireless sensor network, Mobile Networks and Applications, v.10 n.1-2, p.151-168, February 2005 [doi>10.1145/1046430.1046442]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General

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

General Terms:
Algorithms, Design, Performance

Keywords:
aggregating and forwarding nodes, bipartite, multi-training