An Efficient Search Algorithm for Multi-hop Network Localization in a Sparse Unit Disk Graph Model
Article Sidebar
Main Article Content
Abstract
We consider a network localization problem by modeling this as a unit disk graph where nodes are randomly placed with uniform distribution in an area.The connectivity between nodes is defined when the distances fall within a unit range. Under a condition that certain nodes know their locations (anchor nodes), this paper proposes a heuristic approach to find a realization for the rest of the network by applying a tree search algorithm in a depth- first search manner. Our contribution is to put together a priori information and constraints such as graph properties in order to speed up the search. An evaluation function is formed and used to prune down the search space. This evaluation function is used to select the order of the unknown nodes to iterate. This paper also extends the idea further by accommodating a variety of other properties of graphs into the evaluation function. The results show that node degrees, node distances and shortest paths to anchor nodes drastically reduce the number of iterations required for realizing a feasible localization instance both in noise-free and noisy environments. Finally, some preliminary complexity analysis is also given.
Article Details
References
Kaewprapha, P.; Jing Li; Puttarak, N., "Network Localization on Unit Disk Graphs," in Global Telecommunications Conference (GLOBECOM 2011), 2011 IEEE , vol., no., pp.1-5, 5-9 Dec. 2011.
Kaewprapha, P..,”Localization in Wireless Sensor Networks: Solvability Improvement Technique using Priori Information from Sensing Data and Network Properties in Unit Disk Graph Model”, Advanced Materials Research 2014, Issue 931-932, pp99-1003, 5p.
Long Cheng, Chengdong Wu, Yunzhou Zhang, Hao Wu, Mengxin Li, and Carsten Maple, “A Survey of Localization in Wireless Sensor Network,” International Journal of Distributed Sensor Networks, vol. 2012, Article ID 962523, 12 pages, 2012.
Mao G, Fidan B, Anderson BD. “Wireless sensor network localization techniques”, Computer networks. 2007;51(10):2529–2553.
A Pal, “Localization algorithms in wireless sensor networks: Current approaches and future challenges”, Network Protocols and Algorithms, Vol. 2, No. 1.
Heinz Breu, David G. Kirkpatrick, “Unit disk graph recognition is NP-hard”, Computational Geometry, Volume 9, Issues 1–2, January 1998.
Niculescu D, Nath B., “DV based positioning in ad hoc networks”, Telecommunication Systems. 2003;22(1-4):267–280.
A. T. Ihler, J. W. Fisher, R. L. Moses and A. S. Willsky, "Nonparametric belief propagation for self-localization of sensor networks," in IEEE Journal on Selected Areas in Communications, vol. 23, no. 4, pp. 809-819, April 2005.
S. Lee, H. Woo, and C Lee, “Wireless sensor network localization with connectivity-based refinement using mass spring and Kalman filtering,” EURASIP J Wireless Commun. and Networking, pp. 1-11, 2012.
Jun Xiang; Wei Wei Tan, "An improved DV-hop algorithm based on iterative computation for wireless sensor network localization," in Electromagnetics (iWEM), 2013 IEEE International Workshop on , vol., no., pp.171-174, 1-3 Aug. 2013.
Ji S, Sze KF, Zhou Z, So AMC, Ye Y. “Beyond convex relaxation: A polynomial-time non-convex optimization approach to network localization.”, In: INFOCOM, 2013 Proceedings IEEE. IEEE; 2013. p. 2499–2507.
Oliva, G.; Panzieri, S.; Pascucci, F.; Setola, R., "Sensor Networks Localization: Extending Trilateration via Shadow Edges," in Automatic Control, IEEE Transactions on , vol.60, no.10, pp.2752-2755, Oct. 2015.
Nguyen C, Georgiou O, et al. Maximum likelihood based multihop localization in wireless sensor networks. In: Communications (ICC), 2015 IEEE International Conference on. IEEE; 2015. p. 6663–6668.
Aspnes, J.; Eren, T.; Goldenberg, D.K.; Morse, A.S.; Whiteley, W.; Yang, Y.R.; Anderson, B.D.O.; Belhumeur, P.N., "A Theory of Network Localization," in Mobile Computing, IEEE Transactions on , vol.5, no.12, pp.1663-1678, Dec. 2006.
Pemmaraju SV, Pirwani IA. Good quality virtual realization of unit disk graphs. 2007;p. 311–322.
Marray Campbell, A. Joseph Hoane Jr., Feng-hsiung Hsu, "Deep Blue", Artifical Intelligence, Vol. 134, Issues 1-2, Jan 202. pp57-83.
Kaewprapha, P., Puttarak, N., Tansarn, T., “Multi-hop network localization in unit disk graph model under noisy measurement using tree-search algorithm with graph-properties-assist traversing selection”, KKU-IENC, Proceeding of, Khon Kaen, Thailand, August 2016.
G.H. Hardy, Ramanujan. Twelve Lectures on Subjects Suggested by His Life and Work, 3rd ed. New York Chelsea; (1999): p.67.
Santal´o, L. A.: "Integral geometry and geometric probability. Encyclopedia of Mathematics and its Applications," Vol. 1. Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1976.
R. B. Ellis, J. L. Martin, and C. H. Yan, “Random geometric graph diameter in the unit ball," Algorithmica 47 (2007), 421-438.