P-Zone: Connectivity-based Packet Path Tracing in Wireless Sensor Networks

LU Xiaopei; DONG Dezun; LIAO Xiangke; PENG Shaoliang

Article Contents

Article Navigation > Chinese Journal of Electronics > 2013 > 22(3): 477-482

LU Xiaopei, DONG Dezun, LIAO Xiangke, et al. “P-Zone: Connectivity-based Packet Path Tracing in Wireless Sensor Networks”. Chinese Journal of Electronics, vol. 22 no. 3.

Citation:

LU Xiaopei, DONG Dezun, LIAO Xiangke, et al. “P-Zone: Connectivity-based Packet Path Tracing in Wireless Sensor Networks”. Chinese Journal of Electronics, vol. 22 no. 3.

LU Xiaopei, DONG Dezun, LIAO Xiangke, et al. “P-Zone: Connectivity-based Packet Path Tracing in Wireless Sensor Networks”. Chinese Journal of Electronics, vol. 22 no. 3.

Citation:

LU Xiaopei, DONG Dezun, LIAO Xiangke, et al. “P-Zone: Connectivity-based Packet Path Tracing in Wireless Sensor Networks”. Chinese Journal of Electronics, vol. 22 no. 3.

PDF( 1140 KB)

P-Zone: Connectivity-based Packet Path Tracing in Wireless Sensor Networks

College of Computer Science, National University of Defense Technology, Changsha 410073, China

Funds: This work is supported by the National Natural Science Foundation of China (No.60903224, No.61202484, No.61272482, No.61170261, No.60903223 and No.61272056), and Hunan Natural Science Foundation (No.11jj4053).

Received Date: 2012-07-01
Rev Recd Date: 2012-09-01
Publish Date: 2013-06-15

Abstract

Abstract

In large-scale Wireless sensor networks (WSNs), the network status is complex and unpredictable, which brings great challenges to practical network design and management. Tracing the route path of each data packet in the network is an important way to observe network behaviors and understand network dynamics. However, tracing the full route path of each packet could be highly challenging, due to the hard resource constraint inWSNs. Our previous work proposes a hash-based path tracing mechanism, and leverages network connectivity and node locations to reduce the computational complexity. However, the node locations may be unavailable in some scenarios. In this work, we further propose a location-free enhancement to the hash-based path tracing mechanism, called P-Zone. P-Zone requires only network connectivity information to reduce the computational complexity. Theoretical analysis and practical simulations are conducted to evaluate the effectiveness and performance of our design. The results indicate that P-Zone can significantly reduce the computational complexity of the hashbased path tracing mechanism, while effectively tracing the full route path of each packet in the network in a real-time manner, and outperforms the state-of-the-art methods.
- Location-free,
- Packet path tracing,
- Restricted witness graph,
- Wireless sensor networks

FullText(HTML)

References(24)

References

T. He, P. Vicaire, T. Yan, Q. Cao et al., “Achieving long-term surveillance in vigilNet”, Proceedings of the 25th IEEE International Conference on Computer Communication (INFOCOM), Bacelona, Spain, pp.1-12, 2006.

G. Barrenetxea, F. Ingelrest, G. Schaefer et al., “SensorScope: Out-of-the-box environmental monitoring”, Proceedings of the 7th ACM/IEEE Conference on Information Processing in Sensor Network (IPSN), St. Louis, MO, USA, pp.332-343, 2008.

X. Mao, X. Miao., Y. He, X.Y. Li and Y. Liu, “CitySee: Urban CO2 monitoring with sensors”, Proceedings of the 31th IEEE International Conference on Computer Communications, Orlando, Florida, USA, pp.1611-1619, 2012.

R. Rajagopal, X. Nguyen, S.C. Ergen and P. Varaiya, “Distributed online simultaneous fault detection for multiple sensors”, Proceedings of the 7th ACM/IEEE Conference on Information Processing in Sensor Networks, St. Louis, Mo, USA, pp.133-144, 2008.

X. Miao, K. Liu, Y. He, Y. Liu and D. Papadias, “Agnostic diagnosis: Discovering silent failures in wireless sensor networks”, Proceedings of the 30th IEEE International Conference on Computer Communications, Shanghai, China, pp.1548-1556, 2011.

Y. Gu, Y. Ji, H. Chen and B. Zhao, “TAPEMAN: Towards an optimal data gathering mechanism in wireless sensor networks”, Chinese Journal of Electronics, Vol.19, pp.594-598, 2010.

Y. Liu, K. Liu and M. Li, “Passive diagnosis for wireless sensor networks”, IEEE/ACM Transactions on Networking, Vol.18, No.4, pp.1132-1144, 2010.

J. Zhao, R. Govindan and D. Estrin, “Sensor network tomography: Monitoring wireless sensor networks”, ACM SIGCOMM Computer Communication Review, Vol.32, No.1, pp.64, 2002.

C.M. Sadler and M. Martonosi, “Data compression algorithms for energy-constrained devices in delay tolerant networks”, Proceedings of the 4th ACM International Conference on Embedded Networked Sensor Systems (SenSys), New York, NY, USA, pp.265-278, 2006.

C. Liu, K. Wu and J. Pei, “An energy-efficient data collection framework for wireless sensor networks by exploiting spatiotemporal correlation”, IEEE Transactions on Parallel and Distributed Systems, Vol.18, No.7, pp.1010-1023, 2007.

P. Wang, R. Dai and I.F. Akyildiz, “Collaborative data compression using clustered source coding for wireless multimedia sensor networks”, Proceedings of the 29th IEEE International Conference on Computer Communication, Piscataway, NJ, USA, pp.1-9, 2010.

Xiaopei Lu, Dezun Dong, Xiangke Liao and Shanshan Li, “PathZip: Packet path tracing in wireless sensor networks”, accepted to be presented in the 9th IEEE International Conference on Mobile Ad hoc and Sensor Systems (MASS), Las Vegas, Nvada, USA, 2012.

Z. Sun and I.F. Akyildiz, “Connectivity in wireless underground sensor networks”, Proceedings of the 7th Annual IEEE Communications Society Conference on Sensor Mesh and Ad Hoc Communications and Networks (SECON), Boston, MA, USA, pp.1-9, 2010.

M.C. Vuran and I.F. Akyildiz, “Cross-layer packet size optimization for wireless terrestrial, underwater, and underground sensor networks”, Proceedings of 27th IEEE International Conference on Computer Communications, Phoenix, AZ, USA, pp.226-230, 2008.

D. Dong, Y. Liu, X. Liao and X.Y. Li, “Fine-grained locationfree planarization in wireless sensor networks”, Proeedings of the 30th IEEE International Conference on Computer Communications, Shanghai, China, pp.1044-1052, 2011.

N. Ramanathan, K. Chang, R. Kapur, L. Girod, E. Kohler and D. Estrin, “Sympathy for the sensor network debugger”, Proceedings of the 3th ACM International Conference on Embedded Networked Sensor Systems, New York, NY, USA, pp.255-267, 2005.

G. Tolle and D. Culler, “Design of an application cooperative management system for wireless sensor networks”, Proceeedings of the 2nd European Workshop on Wireless Sensor Networks (EWSN), Istanbul, Turkey, pp.121-132, 2005.

Z. Lin, F. Zhao, H. Luo, Y. Ma and X. Yang, “DRMA: A dynamically reconfigurable management architecture for wireless sensor networks”, Chinese Journal of Electronics, Vol.21, pp.350-354, 2012.

A. Woo, T. Tong and D. Culler, “Taming the underlying challenges of reliable multihop routing in sensor networks”, Proceedings of the 1th ACM International Conference on Embedded Networked Sensor Systems, New York, NY, USA, pp.14-27, 2003.

X. Cui, S. Yang, X. Zhang and Z. Liu, “A novel neighboring propagation algorithm based on hierarchical routing scheme for power constrained wireless sensor networks”, Chinese Journal of Electronics, Vol.21, pp.327-331, 2012.

H. Luo, J. Lin and Y. Sun, “A service-centric networking scheme for wireless sensor networks”, Chinese Journal of Electronics, Vol.21, pp.528-534, 2012.

D. Dong, Y. Liu, K. Liu and X. Liao, “Distributed coverage in wireless ad hoc and sensor networks by topological graph approaches”, Proceedings of the 30th IEEE International Conference on Distributed Computing Systems (ICDCS), Genova, Italy, pp.106-115, 2010.

Z. Yang and Y. Liu, “Understanding node localizability of wireless ad-hoc network”, Proceedings of the 29th IEEE International Conference on Computer Communications, San Diego, CA, USA, pp.1-9, 2010.

M. Goldberg and T. Spencer, “A new parallel algorithm for the maximal independent set problem”, Proceedings of the 28th Annual Symposium on Foundations of Computer Science (FOCS), Los Angeles, California, USA, pp.161-165, 1987.

Relative Articles

Supplements(0)

Cited By

Proportional views