Email this article 
Open Access
Subscription or Fee Access
Mobile Relay Configuration in Data-Intensive Wireless Sensor Networks
Abstract
Wireless Sensor Networks (WSNs) are increasingly used in data-intensive applications such as micro-climate monitoring, precision agriculture, and audio/video surveillance. A key challenge faced by data-intensive WSNs is to transmit all the data generated within an application’s lifetime to the base station despite the fact that sensor nodes have limited power supplies. We propose using low-cost disposable mobile relays to reduce the energy consumption of data-intensive WSNs. Our approach differs from previous work in two main aspects. First, it does not require complex motion planning of mobile nodes, so it can be implemented on a number of low-cost mobile sensor platforms. Second, we integrate the energy consumption due to both mobility and wireless transmissions into a holistic optimization framework. Our framework consists of three main algorithms. The first algorithm computes an optimal routing tree assuming no nodes can move. The second algorithm improves the topology of the routing tree by greedily adding new nodes exploiting mobility of the newly added nodes. The third algorithm improves the routing tree by relocating its nodes without changing its topology. This iterative algorithm converges on the optimal position for each node given the constraint that the routing tree topology does not change. We present efficient distributed implementations for each algorithm that require only limited localized synchronization. Because we do not necessarily compute an optimal topology, our final routing tree is not necessarily optimal. However, our simulation results show that our algorithms significantly outperform the best existing solutions.
Keywords
References
R. Szewczyk, A. Mainwaring, J. Polastre, J. Anderson, andD. Culler, “An analysis of a large scale habitat monitoring application,” in SenSys, 2004.
L. Luo, Q. Cao, C. Huang, T. F. Abdelzaher, J. A. Stankovic, and M. Ward, “Enviromic: Towards cooperative storage and retrieval in audio sensor networks,” in ICDCS, 2007, p. 34.
D. Ganesan, B. Greenstein, D. Perelyubskiy, D. Estrin, and J. Heidemann, “An evaluation of multi-resolution storage for sensor networks,” in SenSys, 2003.
S. R. Gandham, M. Dawande, R. Prakash, and S. Venkatesan, “Energy efficient schemes for wireless sensor networks with multiple mobile base stations,” in Globecom, 2003.
J. Luo and J.-P.Hubaux, “Joint mobility and routing for lifetime elongation in wireless sensor networks,” in INFOCOM, 2005.
Z. M. Wang, S. Basagni, E. Melachrinoudis, and C. Petrioli, “Exploiting sink mobility for maximizing sensor networks lifetime,” in HICSS, 2005.
A. Kansal, D. D. Jea, D. Estrin, and M. B. Srivastava, “Controllably mobile infrastructure for low energy embedded networks,” IEEE Transactions on Mobile Computing, vol. 5, pp. 958–973, 2006.
G. Xing, T. Wang, W. Jia, and M. Li, “Rendezvous designalgorithms for wireless sensor networks with a mobile base station,” in MobiHoc, 2008, pp. 231–240.
D. Jea, A. A. Somasundara, and M. B. Srivastava, “Multiple controlled mobile elements (data mules) for data collection in sensor networks,” in DCOSS, 2005.
R. Shah, S. Roy, S. Jain, and W. Brunette, “Data mules: Modelinga three-tier architecture for sparse sensor networks,” in IEEE SNPA Workshop, 2003.
S. Jain, R. Shah, W. Brunette, G. Borriello, and S. Roy, “Exploiting mobility for energy efficient data collection in wireless sensor networks,” MONET, vol. 11, pp. 327–339, 2006.
W. Wang, V. Srinivasan, and K.-C. Chua, “Using mobile relays to prolong the lifetime of wireless sensor networks,” in MobiCom, 2005.
D. K. Goldenberg, J. Lin, and A. S. Morse, “Towards mobility as a network control primitive,” in MobiHoc, 2004, pp. 163–174.
A. A. Somasundara, A. Ramamoorthy, and M. B. Srivastava, “Mobile element scheduling with dynamic deadlines,” IEEETransactions on Mobile Computing, vol. 6, pp. 395–410, 2007.
Y. Gu, D. Bozdag, and E. Ekici, “Mobile element based differentiated message delivery in wireless sensor networks,” in WoWMoM, 2006.
K. Dantu, M. Rahimi, H. Shah, S. Babel, A. Dhariwal, and G. S. Sukhatme, “Robomote: enabling mobility in sensor networks,” in IPSN, 2005.
http://www.k-team.com/robots/khepera/index.html.
J.-H. Kim, D.-H.Kim, Y.-J.Kim, and K.-T. Seow, Soccer Robotics. Springer, 2004.
G. Xing, T. Wang, Z. Xie, and W. Jia, “Rendezvous planning in wireless sensor networks with mobile elements,” IEEETransactions on Mobile Computing, vol. 7, pp. 1430–1443, 2008.
——, “Rendezvous planning in mobility-assisted wireless sensor networks,” in RTSS ’07: Proceedings of the 28th IEEE InternationalReal-Time Systems Symposium, 2007, pp. 311–320.
C.-C. Ooi and C. Schindelhauer, “Minimal energy path planning for wireless robots,” in ROBOCOMM, 2007, p. 2.
C. Tang and P. K. McKinley, “Energy optimization under informed mobility,” IEEE Trans. Parallel Distrib.Syst., vol. 17, pp. 947–962, 2006.
E. D. Demaine, M. Hajiaghayi, H. Mahini, A. S. Sayedi- Roshkhar, S. Oveisgharan, and M. Zadimoghaddam, “Minimizing movement,” in Proceedings of the eighteenth annualACM-SIAM symposium on Discrete algorithms, ser. SODA ’07, 2007, pp. 258–267.
O. Tekdas, Y. Kumar, V. Isler, and R. Janardan, “Building a communication bridge with mobile hubs,” in AlgorithmicAspects of Wireless Sensor Networks, S. Dolev, Ed. Springer- Verlag, 2009, pp. 179–190.
Y. Mei, Y.-H. Lu, Y. Hu, and C. Lee, “Deployment of mobilerobots with energy and timing constraints,” Robotics, IEEETransactions on, vol. 22, no. 3, pp. 507 – 522, june 2006.
A. Sipahioglu, G. Kirlik, O. Parlaktuna, and A. Yazici, “Energy constrained multi-robot sensor-based coverage path planning using capacitated arc routing approach,” Robot.Auton. Syst., vol. 58, pp. 529–538, May 2010.
M. Karpinski and A. Zelikovsky, “New approximation algorithms for the steiner tree problems,” J. Comb. Optim., vol. 1, no. 1, pp. 47–65, 1997.
G. Robins and A. Zelikovsky, “Tighter bounds for graph steiner tree approximation,” SIAM J. Discrete Math., vol. 19, no. 1, pp. 122–134, 2005.
S. Arora, “Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems,” J.ACM, vol. 45, pp. 753–782, September 1998.
K. Jain and V. V. Vazirani, “Approximation algorithms for metric facility location and k-median problems using the primaldualschema and lagrangian relaxation,” J. ACM, vol. 48, pp. 274–296, March 2001.
M. Mahdian, Y. Ye, and J. Zhang, “Improved approximation algorithms for metric facility location problems,” in Proceedingsof the 5th International Workshop on Approximation Algorithms forCombinatorial Optimization, ser. APPROX ’02, 2002, pp. 229–242.
L. Wang and Y. Xiao, “A survey of energy-efficient scheduling mechanisms in sensor networks,” Mob. Netw.Appl., vol. 11, pp. 723–740, 2006.
G. Wang, M. J. Irwin, P. Berman, H. Fu, and T. F. L. Porta, “Optimizing sensor movement planning for energy efficiency,” in ISLPED, 2005, pp. 215–220.
“Cc2420 datasheet,” http://inst.eecs.berkeley.edu/cs150/Documents/CC2420.pdf.
“Cc1000 single chip very low power rf transceiver.” http://focus.ti.com/lit/ds/symlink/cc1000.pdf.
M. Sha, G. Xing, G. Zhou, S. Liu, and X.Wang, “C-mac: Modeldrivenconcurrent medium access control for wireless sensor networks,” in INFOCOM, 2009.
W. R. Heinzelman, A. Chandrakasan, and H. Balakrishnan, “Energy-efficient communication protocol for wireless microsensornetworks,” in HICSS, 2000.
S. Ratnasamy, B. Karp, S. Shenker, D. Estrin, R. Govindan, L. Yin, and F. Yu, “Data-centric storage in sensornets with ght, a geographic hash table,” MONET, vol. 8, pp. 427–442, 2003.
C. E. Perkins and E. M. Royer, “Ad-hoc on-demand distance vector routing,” in WMCSA ’99: Proceedings of the SecondIEEE Workshop on Mobile Computer Systems and Applications. Washington, DC, USA: IEEE Computer Society, 1999, p. 90.
Refbacks
- There are currently no refbacks.
This work is licensed under a Creative Commons Attribution 3.0 License.