Your browser does not support JavaScript!
http://iet.metastore.ingenta.com
1887

access icon free Obstacle-avoidance path planning of a mobile Beacon for localisation

  • Author(s): Yinglong Wang 1 ; Huanqing CUI 1, 2 ; Qiang GUO 3 ; Minglei SHU 1
    • View affiliations
    • Affiliations: 1: Shandong Provincial Key Laboratory of Computer Network, Shandong Computer Science Center, Ji'nan, Shandong 250014, People's Republic of China;
      2: College of Information Science and Engineering, Shandong University of Science and Technology, Qingdao, Shandong 266590, People's Republic of China;
      3: School of Information and Management, Shandong Economic University, Ji'nan, Shandong 250061, People's Republic of China
  • Source: Volume 3, Issue 2, June 2013, p. 126 – 137
    DOI:  10.1049/iet-wss.2011.0128 , Print ISSN 2043-6386, Online ISSN 2043-6394
© The Institution of Engineering and Technology
Received 23/08/2011, Accepted 03/12/2012, Revised 23/11/2012, Published

Location is important for most wireless sensor network applications. A potential localisation method uses a mobile beacon instead of numerous static beacons. This method includes planning a beacon trajectory as a fundamental and interesting problem. Obstacles in practical scenarios often restrict the free locomotion of beacons. This study examines the obstacle-avoidance path-planning method, which consists of three stages. First, the network deployment region is partitioned into cells by adaptive cell decomposition, and the corresponding connectivity graph is constructed. Second, a modified max–min ant system algorithm is provided to obtain the approximate shortest global path that covers the connectivity graph. Finally, a sequence of concentric circles of adjustable radii is utilised as the local path within an obstacle-free cell. We prove that all sensor nodes deployed in obstacle-free cells can be localised by using the proposed path. Simulation results show that more than 90% of the sensor nodes in the obstacle-free region can be localised by using the given trajectory.

Inspec keywords: ant colony optimisation; wireless sensor networks; collision avoidance; network theory (graphs); minimax techniques; sensor placement

Other keywords: obstacle avoidance path planning method; sensor localisation method; connectivity graph; mobile beacon; beacon locomotion; max–min ant system algorithm; sensor node deployment; wireless sensor network; shortest global path approximation; max–min ant system algorithm; network deployment region partitioning; adaptive cell decomposition; beacon trajectory planning; obstacle free cell

Subjects: Wireless sensor networks; Optimisation techniques; Mobile radio systems; Combinatorial mathematics

References

    1. 1)
      • 14. Guerrero, E., Xiong, H.G., Gao, Q., Ricardo, R., Estévez, J.: ‘ADAL: a distributed range-free localization algorithm based on a mobile beacon for wireless sensor netwoks’. Proc. Int. Conf. on Ultra Modern Telecommunication, St.-Petersburg, Russia, October, 2009. pp. 1–7.
    2. 2)
      • 20. Li, H., Bu, Y., Xue, H., Li, X., Ma, H.: ‘Path planning for mobile anchor node in localization for wireless sensor networks’, J. Comput. Res. Dev., 2009, 46, (1), pp. 129–136.
    3. 3)
      • 7. Zhao, F., Luo, H., Lin, Q.: ‘A mobile beacon-assisted localization algorithm based on network-density clustering for wireless sensor networks’. Proc. Fifth Int. Conf. on Mobile Ad-hoc Sensor Networking, Wuxi, China, December, 2009. pp. 304–310.
    4. 4)
      • 10. Chen, H., Liu, B., Huang, P., Liang, J.: ‘Mobility-assisted node localization based on TOA measurements without time synchronization in wireless sensor networks’, ACM/Springer Mobile Netw. Appl., 2012, 17, (1), pp. 90–99 (doi: 10.1007/s11036-010-0281-3).
    5. 5)
      • 15. Chen, Y.-S., Ting, Y.-J., Ke, C.-H., Chilamkruti, N., Park, J.H.: ‘An efficient localization scheme with ring overlapping by utilizing mobile anchors in wireless sensor networks’. Proc. Fourth Int. Conf. on Multimedia Ubiquitous Eng., Cebu, Philippines, August, 2010, pp. 1–6.
    6. 6)
      • 4. Chen, H., Chan, Y.T., Poor, H.V., Sezaki, K.: ‘Range-free localization with radical line’. Proc. IEEE Int. Conf. Communication, Cape Town, South Africa, May, 2010, pp. 1–5.
    7. 7)
      • 21. Li, S., Xu, C., Yang, Y., Pan, Y.: ‘Getting mobile beacon path for sensor localization’, J. Software, 2008, 19, (2), pp. 455–467 (doi: 10.3724/SP.J.1001.2008.00369).
    8. 8)
      • 18. Huang, R., Zaruba, G.V.: ‘Static path planning for mobile beacons to localize sensor networks’. Proc. Fifth Annual IEEE Int. Conf. on Pervasive Comput. Commun., New York, USA, March, 2007, pp. 323–330.
    9. 9)
      • 11. Guo, Z., Guo, Y., Hong, F., Jin, Z., He, Y., Feng, Y., et al: ‘Perpendicular intersection: locating wireless sensors with mobile beacon’, IEEE Trans. Veh. Technol., 2010, 59, (7), pp. 3501–3509 (doi: 10.1109/TVT.2010.2049391).
    10. 10)
      • 25. Choset, H., Lynch, K.M., Hutchinson, S., Kantor, G., Burgard, W., Kavraki, L.E., et al: ‘Principles of robot motion: theory, alogrithms, and implementations’ (MIT Press, 2005).
    11. 11)
      • 6. Bahi, J.M., Makhoul, A.: ‘A mobile beacon based approach for sensor network localization’. Proc. Third IEEE Int. Conf. on Wireless Mobile Computation, Networking Communication, New York, USA, October, 2007, pp. 44–48.
    12. 12)
      • 29. Martins, M.H., Chen, H., Sezaki, K.: ‘OTMCL: Orientation tracking-based Monte Carlo localization for mobile sensor networks,’ Proc. Sixth Int. Conf. on Netw. Sensing Syst., Pittsburgh, USA, June, 2009, pp. 1–8.
    13. 13)
      • 23. Wei, Y., Li, R., Chen, H., Luo, J.: ‘Path planning of mobile beacon for localizatioin in wireless sensor network’, J. Syst. Simul., 2009, 21, (22), pp. 7258–7261.
    14. 14)
      • 30. Chen, H., Martins, M.H., Huang, P., So, H.C., Sezaki, K.: ‘Cooperative node localization for mobile sensor networks,’ Proc. Int. Conf. on Embedded Ubiquitous Comput., vol. I, Shanghai, China, December, 2008, pp. 302–308.
    15. 15)
      • 9. Ding, Y., Wang, C., Xiao, L.: ‘Using mobile beacons to locate sensors in obstructed environments’, J. Parallel Distrib Comput., 2010, 70, (6), pp. 644–656 (doi: 10.1016/j.jpdc.2010.03.002).
    16. 16)
      • 27. Stützle, T., Hoos, H.H.: ‘Max-min ant system’, Future Gener. Comput. Syst., 2000, 16, (8), pp. 889–914 (doi: 10.1016/S0167-739X(00)00043-1).
    17. 17)
      • 8. Liu, K., Xiong, J.: ‘A fine-grained localization scheme using a mobile beacon node for wireless sensor networks’, J. Inf. Process. Syst., 2010, 6, (2), pp. 147–162.
    18. 18)
      • 24. Cui, H., Wang, Y., Guo, Q., Wei, N.: ‘Getting obstacle avoidance trajectory of mobile beacon for localization’, Int. J. Comput. Netw. Inf. Security, 2010, 2, (1), pp. 45–51 (doi: 10.5815/ijcnis.2010.01.07).
    19. 19)
      • 19. Fu, Q., Chen, W., Liu, K., Chen, W., Wang, X.: ‘Study on mobile beacon trajectory for node localization in wireless sensor networks’. Proc. IEEE Int. Conf. Inf. Autom., Harbin, China, June, 2010, pp. 1577–1581.
    20. 20)
      • 5. Sichitiu, M.L., Ramadurai, V.: ‘Localization of wireless sensor networks with a mobile beacon’. Proc. IEEE Int. Conf. Mobile Ad-hoc Sensor Systems, Fort Lauderdale, USA, October, 2004, pp. 174–183.
    21. 21)
      • 28. Zhou, Y.: ‘Runtime analysis of an ant colony optimization algorithm for TSP instances’, IEEE Trans. Evoluat. Comput., 2009, 13, (5), pp. 1083–1092 (doi: 10.1109/TEVC.2009.2016570).
    22. 22)
      • 2. Chen, H., Sezaki, K., Deng, P., So, H.C.: ‘An improved DV-Hop localization algorithm with reduced node location error for wireless sensor networks’, IEICE Trans. Fundam. Electron. Commun. Comput. Sci., 2008, E91-A, (8),pp. 2232–2236 (doi: 10.1093/ietfec/e91-a.8.2232).
    23. 23)
      • 13. Lee, S., Kim, E., Kim, C., Kim, K.: ‘Localization with a mobile beacon based on geometric constraints in wireless sensor networks’, IEEE Trans. Wirel. Commun., 2009, 8, (12), pp. 5801–5805 (doi: 10.1109/TWC.2009.12.090319).
    24. 24)
      • 3. Shi, Q., He, C., Chen, H., Jiang, L.: ‘Distributed wireless sensor network localization via sequential greedy optimization algorithm’, IEEE Trans. Signal Process., 2010, 58, (6), pp. 3328–3340 (doi: 10.1109/TSP.2010.2045416).
    25. 25)
      • 22. Hu, B., Li, H., Liu, S.: ‘Getting mobile beacon node path in wsn based on ant colony algorithm’. Proc. Int. Conf. on Compuat. Intell. Nat. Comput., Wuhan, China, June, 2009, pp. 22–25.
    26. 26)
      • 16. Chen, H., Shi, Q., Tan, R., Poor, H.V., Sezaki, K.: ‘Mobile element assisted cooperative localization for wireless sensor networks with obstacles’, IEEE T. Wirel. Commun., 2010, 9, (3), pp. 956–963 (doi: 10.1109/TWC.2010.03.090706).
    27. 27)
      • 12. Xiao, B., Chen, H., Zhou, S.: ‘Distributed localization using a moving beacon in wireless sensor networks’, IEEE Trans. Parallel Distr. Syst., 2008, 19, (5), pp. 587–600 (doi: 10.1109/TPDS.2007.70773).
    28. 28)
      • 26. Dorigo, M., Birattari, M., Stützle, T.: ‘Ant colony optimization’, IEEE Comput. Intell. M., 2006, 1, (4), pp. 28–39.
    29. 29)
      • 1. Liu, Y., Yang, Z., Wang, X., Jian, L.: ‘Location, localization, and localizability’, J. Comput. Sci. Technol., 2010, 25, (2), pp. 274–297 (doi: 10.1007/s11390-010-9324-2).
    30. 30)
      • 17. Koutsonikolas, D., Das, S.M., Hu, Y.C.: ‘Path planning of mobile landmarks for localization in wireless sensor networks’, Comput. Commun., 2007, 30, (13), pp. 2577–2592 (doi: 10.1016/j.comcom.2007.05.048).
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-wss.2011.0128
Loading

Related content

content/journals/10.1049/iet-wss.2011.0128
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading
Print this page
This is a required field
Please enter a valid email address