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.
Full Text:
PDFReferences
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.
This work is licensed under a Creative Commons Attribution 3.0 License.