Bipartivity Index based Link Selection Strategy to Determine Stable and Energy-Efficient Data Gathering Trees for Mobile Sensor Networks
Abstract
Bipartivity Index (BPI) has been used in complex network analysis to quantify the extent of partitioning of the vertices of a network graph into two disjoint partitions; the edges between vertices within the same partition are called frustrated edges. The BPI values for a network graph ranges from 0 to 1 (the BPI of a network graph that is truly bipartite and has no frustrated edges is 1). Our hypothesis in this research is that the end nodes of a short distance link (the distance between the end nodes is significantly smaller than the transmission range per node) in a mobile sensor network (MSN) are more likely to share a significant fraction of their neighbors and such links are more likely to be stable. We introduce a notion called the egocentric network of an edge (adapted from egocentric network for a node) comprising of the end nodes of the edge and their neighbors (as vertices) and the edges incident on the end nodes (as edges). Our claim is that an edge whose egocentric network has a lower BPI score is more likely to be a stable short distance link, with a relatively larger fraction of shared neighborhood, and could be preferred for inclusion while determining stable data gathering trees for MSNs. Through extensive simulations, we show that the BPI-based DG trees are significantly more stable and energy-efficient compared to the DG trees determined using the predicted link expiration time (LET), currently the best known strategy.References
B. Hull, V. Bychkovsky, Y. Zhang, K. Chen, M. Goraczko, A. Miu, E. Shih, H. Balakrishnan and S. Madden, “CarTel: A Distributed Mobile Sensor Computing System,” Proceedings of the 4th International Conference on Embedded Networked Sensor Systems, pp. 125-138, Boulder, CO, USA, November 2006.
S. Lindsey, C. Raghavendra and K. M. Sivalingam, "Data Gathering Algorithms in Sensor Networks using Energy Metrics," IEEE Transactions on Parallel and Distributed Systems, vol. 13, no. 9, pp. 924-935, September 2002.
W. Heinzelman, A. Chandrakasan and H. Balakarishnan, “Energy-Efficient Communication Protocols for Wireless Microsensor Networks,” Proceedings of the Hawaaian International Conference on Systems Science, Maui, HI, USA, January 2000.
N. Meghanathan, "A Comprehensive Review and Performance Analysis of Data Gathering Algorithms for Wireless Sensor Networks," International Journal of Interdisciplinary Telecommunications and Networking, vol. 4, no. 2, pp. 1-29, April-June 2012.
N. Meghanathan, “A Data Gathering Algorithm based on Energy-aware Connected Dominating Sets to Minimize Energy Consumption and Maximize Node Lifetime in Wireless Sensor Networks,” International Journal of Interdisciplinary Telecommunications and Networking, vol. 2, no. 3, pp. 1-17, July-September 2010.
N. Meghanathan, "Link Expiration Time and Minimum Distance Spanning Trees based Distributed Data Gathering Algorithms for Wireless Mobile Sensor Networks," International Journal of Communication Networks and Information Security, vol. 4, no. 3, pp. 196-206, December 2012.
W. Su and M. Gerla, “IPv6 Flow Handoff in Ad hoc Wireless Networks using Mobility Prediction,” Proceedings of the IEEE Global Telecommunications Conference, pp. 271-275, December 1999.
N. Meghanathan, Recent Advances in Ad Hoc Networks Research, Nova Science Publishers, August 2014.
N. Meghanathan, "A Generic Algorithm to Determine Maximum Bottleneck Node Weight-based Data Gathering Trees for Wireless Sensor Networks," Network Protocols and Algorithms, vol. 7, no. 3, pp. 18-51, November 2015.
T. S. Rappaport, Wireless Communications: Principles and Practice, 2nd edition, Prentice Hall, January 2002.
B. Hofmann-Wellenhof, H. Lichtenegger and J. Collins, Global Positioning System: Theory and Practice, 5th Edition, Springer, October 2013.
E. Estrada and J. A. Rodriguez-Velazquez, "Spectral Measures of Bipartivity in Complex Networks," Physical Review E 72, 046105, pp. 1-6, 2005.
P. V. Marsden, "Egocentric and Sociocentric Measures of Network Centrality," vol. 24, no. 4, pp. 407-422, October 2002.
N. Meghanathan, "Routing Protocols to Determine Stable Paths and Trees using the Inverse of Predicted Link Expiration times for Mobile Ad hoc Networks," International Journal of Mobile Network Design and Innovation, vol. 4, no. 4, pp. 214-234, June 2012.
N. Meghanathan, "Exploring the Performance Tradeoffs among Stability-Oriented Routing Protocols for Mobile Ad hoc Networks," Network Protocols and Algorithms – Special Issue on Data Dissemination for Large scale Complex Critical Infrastructures, vol. 2, no. 3, pp. 18-36, November 2010.
H. Zhang and J. C. Hou, "Maintaining Sensing Coverage and Connectivity in Large Sensor Networks," Wireless Ad hoc and Sensor Networks: An International Journal, vol. 1, no. 1-2, pp. 89-123, January 2005.
A. J. Viterbi, CDMA: Principles of Spread Spectrum Communication, 1st Edition, Prentice Hall, April 1995.
D. Tao, S. Tang and H. Ma, "Low Cost Data Gathering using Mobile Hybrid Sensor Networks," Lecture Notes in Computer Science, vol. 7363, pp. 193-206, July 2012.
M. Ma and Y. Yang, "SenCar: An Energy-Efficient Data Gathering Mechanism for Large-Scale Multihop Sensor Networks," IEEE Transactions on Parallel and Distributed Systems, vol. 18, no. 10, pp. 1476-1488, October 2007.
Y-C. Tseng, F-J. Wu and W-T. Lai, "Opportunistic Data Collection for Disconnected Wireless Sensor Networks by Mobile Mules," Ad Hoc Networks, vol. 11, no. 3, pp. 1150-1164, May 2013.
Y. Lai, J. Xie, Z. Lin, T. Wang and M. Liao, "Adaptive Data Gathering in Mobile Sensor Networks using Speedy Mobile Elements," Sensors, vol. 15, no. 9, pp. 23218-23248, 2015.
T. Banerjee, B. Xie, J. H. Jun and D. P. Agarwal, "LIMOC: Enhancing the Lifetime of a Sensor Network with Mobile Clusterheads," Proceedings of the Vehicular Technology Conference Fall, pp. 133-137, Baltimore, MD, USA, September 30 - October 3, 2007.
G. Santhosh Kumar, M. V. Vinu Paul and K. Jacob Poulose, "Mobility Metric based LEACH-Mobile Protocol," Proceedings of the 16th International Conference on Advanced Computing and Communications, pp. 248-253, Chennai, India, December 2008.
S. Deng, J. Li and L. Shen, "Mobility-based Clustering Protocol for Wireless Sensor Networks with Mobile Nodes," IET Wireless Sensor Systems, vol. 1, no. 1, pp. 39-47, March 2011.
C-M. Liu, C-H. Lee and L-C. Wang, "Distributed Clustering Algorithms for Data Gathering in Wireless Mobile Sensor Networks," Journal of Parallel and Distributed Computing, vol. 67, no. 11, pp. 1187-1200, November 2007.
H. K. D. Sarma, R. Mall and A. Kar, "E2R2: Energy-Efficient and Reliable Routing for Mobile Wireless Sensor Networks," IEEE Systems Journal, vol. 10, no. 2, pp. 604-616, April 2015.
R. Velmani and B. Kaarthick, "An Energy Efficient Data Gathering in Dense Mobile Wireless Sensor Networks," International Scholarly Research Notices Sensor Networks, vol. 2014, Article ID: 518268, 10 pages, 2014.
M. Macuha, M. Tariq and T. Sato, "Data Collection Method for Mobile Sensor Networks Based on the Theory of Thermal Fields," Sensors, vol. 11, no. 7, pp. 7188-7203, July 2011.
N. Meghanathan and P. Mumford, "A Benchmarking Algorithm to Determine the Sequence of Stable Data Gathering Trees for Wireless Mobile Sensor Networks," Informatica – An International Journal of Computing and Informatics, vol. 37, no. 3, pp. 315-338, October 2013.
N. Meghanathan, "A Greedy Algorithm for Neighborhood Overlap-based Community Detection," Algorithms, vol. 9, no. 1, p. 8: 1-26, 2016.
P. De Meo, E. Ferrara, G. Fiumara and A. Provetti, "On Facebook, Most Ties are Weak," Communications of the ACM, vol. 57, no. 11, pp. 78-84, November 2014.
N. Meghanathan, "A Benchmarking Algorithm to Determine Minimum Aggregation Delay for Data Gathering Trees and an Analysis of the Diameter-Aggregation Delay Tradeoff," Algorithms, vol. 8, no. 3, pp. 435-458, July 2015.
N. Meghanathan, "Stability-based and Energy-Efficient Distributed Data Gathering Algorithms for Mobile Sensor Networks," Ad hoc Networks, vol. 19, pp. 111-131, August 2014.
C. Bettstetter, H. Hartenstein and X. Perez-Costa, “Stochastic Properties of the Random-Way Point Mobility Model,” Wireless Networks, vol. 10, no. 5, pp. 555-567, September 2004.
Abolhasan, M., Wysocki, T., Dutkiewicz, E., "A Review of Routing Protocols for Mobile Ad hoc Networks," Ad hoc Networks, vol. 2, no. 1, pp. 1-22, 2004.
T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to Algorithms, 3rd Edition, MIT Press, July 2009.
Downloads
Published
How to Cite
Issue
Section
License
I assign to Informatica, An International Journal of Computing and Informatics ("Journal") the copyright in the manuscript identified above and any additional material (figures, tables, illustrations, software or other information intended for publication) submitted as part of or as a supplement to the manuscript ("Paper") in all forms and media throughout the world, in all languages, for the full term of copyright, effective when and if the article is accepted for publication. This transfer includes the right to reproduce and/or to distribute the Paper to other journals or digital libraries in electronic and online forms and systems.
I understand that I retain the rights to use the pre-prints, off-prints, accepted manuscript and published journal Paper for personal use, scholarly purposes and internal institutional use.
In certain cases, I can ask for retaining the publishing rights of the Paper. The Journal can permit or deny the request for publishing rights, to which I fully agree.
I declare that the submitted Paper is original, has been written by the stated authors and has not been published elsewhere nor is currently being considered for publication by any other journal and will not be submitted for such review while under review by this Journal. The Paper contains no material that violates proprietary rights of any other person or entity. I have obtained written permission from copyright owners for any excerpts from copyrighted works that are included and have credited the sources in my article. I have informed the co-author(s) of the terms of this publishing agreement.
Copyright © Slovenian Society Informatika
