Overdue-beacon-aided Localization Algorithm in Mobile Sensor Networks

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：31

、訪客IP：18.218.38.67

姓名

黃任鋒(Jen-Feng Huang) 查詢紙本館藏

畢業系所

資訊工程學系

論文名稱

(Overdue-beacon-aided Localization Algorithm in Mobile Sensor Networks)

相關論文

★ 基於OP-TEE的可信應用程式軟體生態系統	★ SeFence: 基於安全感測的可信任周邊存取控制
★ 高解析度二維地理影像的三維建模：旋轉變換投影與傳統方法的比較研究	★ 在低軌道衛星無線通訊中的CSI預測方法
★ 為多流量低軌道衛星系統提出的動態換手策略	★ 基於Trustzone的智慧型設備語音隱私保護系統
★ 一種減輕LEO衛星網路干擾的方案	★ TruzGPS:基於TrustZone的位置隱私權保護系統
★ 衛星地面整合網路之隨機接入前導訊號設計與偵測	★ SatPolicy: 基於Trustzone的衛星政策執行系統
★ TruzMalloc: 基於TrustZone 的隱私資料保護系統	★ 衛星地面網路中基於物理層安全的CSI保護方法
★ 低軌道衛星地面整合網路之安全非正交多重存取傳輸	★ 低軌道衛星地面網路中的DRX機制設計
★ 衛星地面整合網路之基於集合系統的前導訊號設計	★ 基於省電的低軌衛星網路路由演算法

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

在無線感測網路中，定位資訊的重要性不言可喻。雖然過去有許多演算法被提出。但定位精確度在移動式的感測網路仍然需要被改善。然而在改善的同時通常伴隨的是付出另外一個更大的代價─communication cost。用傳遞多hop的技術與跟鄰居交換資訊卻可能帶來sensor networks不可承擔的通訊負擔，甚至是廣播風暴的問題。在本論文中, 我們不增加任何communication cost就達到定位精確度提升。我們利用三種zero cost的資訊，通訊半徑、收到的訊號強度以及過去的beacon，定位sensor。更值得注意的是我們的定位演算法比其他種演算法更適合用於低密度的anchor node環境下。低密度的anchor node環境對於一個sensor networks除了節省communication cost之外，更能縮減佈建成本。

摘要(英)

In wireless sensor networks, the location information has major impact on many applications. The localization accuracy is not good enough, although substantial studies have been proposed to solve this problem on mobile sensor networks. Unfortunately, a large amount of resources, the communication cost, must be sacrificed in terms of promoting the localization accuracy. Using the technologies that broadcast multi-hop anchor information and exchange the neighbor information will cause hung communication cost that the sensor networks can’t work well and it will bring broadcast storm problem. In this thesis, we enhance the localization accuracy without increase any communication cost. In our proposed algorithm, we use three known information which are communication range, received RSS of beacon, and overdue beacons to locate normal node. It is noteworthy that our proposed algorithm performance is better than others algorithms in sparse anchor environments. Not only reduce device cost, but also reduce communication cost in low anchor density scenario.

關鍵字(中)

★ 移動式網路
★ 定位演算法

關鍵字(英)

★ mobile sensor networks
★ range-free localization algorithm
★ useless beacon pair

論文目次

Contents
Chapter 1 Introduction 1
Chapter 2 Related Works 4
2.1 Localization algorithm for static normal nodes: Connectivity-based algorithm 5
2.2 Localization algorithm for static normal nodes: non connectivity -based algorithm 6
2.3 Localization algorithm for mobile normal nodes: Connectivity-based algorithm 7
2.4 Localization algorithm for mobile normal nodes: Non connectivity-based algorithm 11
2.5 Problem statement 12
Chapter 3 Overdue-Beacon-Aided Localization Algorithm 14
3.1 Environment and Assumptions 14
3.2 Sparse beacon environments 14
3.2.1 One dimensional moving space 14
3.2.2 Two dimensional moving space 16
3.3 The proposed algorithm for sparse beacon environments 19
3.4 Normal node without hearing any beacon in current slot 23
3.5 The proposed algorithm for normal nodes without hearing any beacon 27
Chapter 4 Analysis 30
4.1 Special-case: Comparison the anchor’s RSS information in the same time slot 30
4.2 Performance analysis 31
Chapter 5 Simulation 35
5.1 Communication Cost 36
5.2 Localization Error in Random-way-point model 37
5.3 Anchor Nodes Density 39
5.4 Impact of Normal Node Speed 40
5.5 Impact of DOI 42
Chapter 6 Conclusion 44
6.1 Summary our works 44
References 46
Appendix A Addition OBALA into MCL Series Algorithms 49

List of Figures
Figure 1.1 RSS-based Range free Localization Algorithm 3
Figure 2.1 DRLS and LMAP. (a)Error of DRLS. (b)LMAP. 5
Figure 2.2 LMAP-enhance 6
Figure 2.3 APIT. 7
Figure 2.4 Sequence-based. 7
Figure 2.5 MCL algorithm. (a) Sample node of MCL. (b) Filter the sample node using neighbor constraint. (c) Simulate the possible region by sample node. 8
Figure 2.6 MCB Algorithm. (a) Construct the sample box. (c) Modify the sample box form in slot j. 9
Figure 2.7 IMCL Algorithm. (a) Find the sample center C. (b) Find the pie area in IMCL. (c) Decide the possible region by neighbors. 10
Figure 2.8 MMCL Algorithm. (a) Overestimated hop-count. (b) Expected hop-count. 10
Figure 2.9 Idea of LAH. 11
Figure 2.10 Overdue beacon problem. (a) N received the beacons in the same time slot. (b) N received the beacons in the different time slot. 13
Figure 3.1 Compare bi with bj relationship in slot j. (a) case1: System I. (b) Right shifts system I. (c) case2: System I. (d) Left shifts system I. 16
Figure 3.2 The possible position of bi†. 16
Figure 3.3 The possible region of Nj. 19
Figure 3.4 Enhance anchor utilization process by THEOREM 1. 20
Figure 3.5 Vote the possible region. 20
Figure 3.6 System I, system J, system X and System K. (a) System I and system J. (b) System X and D(bi, bi†)=NiNj. (c) System X moves NjNk such that Nj†=Nk. (d) System K and D(bi, bi††)=NiNj+NjNk. 24
Figure 3.7 The possible position of bi††and bj†. 24
Figure 3.8 The possible region of Nk. 27
Figure 4.1 Possible Region for bi, b1, b2, b3, b4. (a) Use communication range. (b) Use communication range and beacon’s RSS relationship. 32
Figure 4.2 Connectivity-based algorithm and OBALA. (a) Connectivity-based algorithm’s possible region. (b) Use OBALA and RSS(bj)>RSS(bi). (c) Use OBALA and RSS(bj)=RSS(bi). (d) Use OBALA and RSS(bi)> RSS(bj). 33
Figure 5.1 OBALA v.s. MCL-1hop 37
Figure 5.2 Localization error in random-way-point model. 38
Figure 5.3 Impact of anchor node density: OBALA/MCL-1hop 38
Figure 5.4 Impact of anchor node density: MCL, IMCL, MCL+OBALA, IMCL+OBALA. 39
Figure 5.5 Step of IMCL. (a)Use anchor constraint. (b)Pie area not include real normal node. (c)Exchange the error information to neighbor node. 40
Figure 5.6 Impact of normal node speed: OBALA/MCL-1hop. 41
Figure 5.7 Impact of normal node speed: MCL, IMCL, MCL+OBALA, IMCL+OBALA. 41
Figure 5.8 Impact of anchor node speed: OBALA/MCL-1hop. 42
Figure 5.9 Impact of DOI: MCL, IMCL, MCL+OBALA. 43

List of Tables
TABLE 2.1 COMPARISON SHEET OF MOBILE LOCALIZATION ALGORITHMS 11
TABLE 5.1 SIMULATION PARAMETERS 36
TABLE 5.2 COMMUNICATION COST 36

List of Procedures
PROCEDURE 1 MAINTAIN POSSIBLE REGION 21
PROCEDURE 2 OVERDUE-BEACON PROCESS WITH NEW BEACON 22
PROCEDURE 3 OVERDUE-BEACON PROCESS WITHOUT NEW BEACON 29

List of Algorithms
ALGORITHM 1 OVERDUE-BEACON-AIDED LOCALIZATION ALGORITHM (SPARSE BEACONS) 22
ALGORITHM 2 OVERDUE-BEACON-AIDED LOCALIZATION ALGORITHM (WITHOUT HEARING BEACON) 29

參考文獻

[1] S. Kumar, T-H. Lai, and A. Arora, “Barrier Coverage With Wireless Sensors,” in Proc. ACM MobiCom, 2005.
[2] Y. Liu et al., “Does wireless sensor network scale? A measurement study on GreenOrbs,” in Proc. IEEE INFOCOM, 2011.
[3] B. Krishnamachari and S. Iyengar, “Distributed Bayesian algorithms for fault-tolerant event region detection in wireless sensor networks,” IEEE Transactions on Computers, vol.53, no.3, 2004.
[4] P. Brass, “Bounds on coverage and target detection capabilities for models of networks of mobile sensors,” ACM Transactions on Sensor Networks, vol.3, no.2, 2007.
[5] A. Navarra, C.M. Pinotti, V. Ravelomanana, F. Betti Sorbelli, and R. Ciotti, “Cooperative training for high density sensor and actor networks,” IEEE Journal on Selected Areas in Communications, vol.28, no.5, 2010.
[6] Yanchao Zhang, Wei Liu, Wenjing Lou, and Yuguang Fang, “Location-based compromise-tolerant security mechanisms for wireless sensor networks,” IEEE Journal on Selected Areas in Communications, vol.24, no.2, 2006.
[7] C. Fischer and H. Gellersen, “Location and Navigation Support for Emergency Responders: A Survey,” IEEE Pervasive Computing, vol.9, no.1, 2010.
[8] L. Blazevic, J.-Y. Le Boudec, and S. Giordano, “A location-based routing method for mobile ad hoc networks,” IEEE Transactions on Mobile Computing, vol.4, no.2, 2005.
[9] B. Karp and H. T. Kung, “GPSR: Greedy Perimeter Stateless Routing for Wireless,” in Proc. ACM MobiCom, 2000.
[10] Y. Zou and K. Chakrabarty, “Sensor deployment and target localization based on virtual forces,” in Proc. IEEE INFOCOM, 2003.
[11] J.-P. Sheu, P.-C. Chen, and C.-S. Hsu, “A distributed localization scheme for wireless sensor networks with improved grid-scan and vector-based refinement,” IEEE Transactions on Mobile Computing, vol.7, no.9, 2008.
[12] K.-F. Ssu, C.-H. Ou, and H.-C. Jiau, “localization with mobile anchor points in wireless sensor networks,” IEEE Transactions on Vehicular Technology, vol.54, no.3, 2005.
[13] T. He, C. Huang, B. M. Blum, J. A. Stankovic, and T. Abdelzaher, “Range-Free Localization Schemes for Large Scale Sensor Networks,” in Proc. ACM MobiCom, 2003.
[14] D. Niculescu and B. Nath, “DV based positioning in ad hoc networks,” Kluwer Journal of Telecommunication Systems, vol.22, no.1, 2003.
[15] K. Yedavalli and B. Krishnamachari, “Sequence-Based Localization in Wireless Sensor Networks,” IEEE Transactions on Mobile Computing, vol.7, no.1, 2008.
[16] P. Tseng, “Second-Order Cone Programming Relaxation of Sensor Network Localization,” SIAM Journal on Optimization, vol.18, no.1, 2007.
[17] Y. Wang, S. Lederer, and J. Gao, “Connectivity-Based Sensor Network Localization with Incremental Delaunay Refinement Method,” in Proc. IEEE INFOCOM, 2009.
[18] D. Niculescu and B. Nath, “Ad hoc positioning system (APS) using AOA,” in Proc. INFOCOM, 2003.
[19] N. Patwari et al., “Locating the nodes: cooperative localization in wireless sensor networks,” IEEE Signal Processing Magazine, vol.22, no.4, 2005.
[20] D. Ampeliotis and K. Berberidis, “Sorted Order-k Voronoi Diagrams for Model-Independent Source Localization in Wireless Sensor Networks,” IEEE Transactions on Signal Processing, vol.58, no.1, 2010.
[21] T. Wark et al., “The Design and Evaluation of a Mobile Sensor/Actuator Network for Autonomous Animal Control,” in Proc. IPSN, 2007.
[22] J. Cortes and F. Bullo, “Coordination and Geometric Optimization via Distributed Dynamical Systems,” SIAM Journal on Control and Optimization, vol.44, no.5, 2005.
[23] L. Hu and D. Evans, “Localization for Mobile Sensor Networks,” in Proc. ACM MobiCom, 2004.
[24] M. Rudafshani and S. Datta, “Localization in Wireless Sensor Networks,” in Proc. IPSN, 2007.
[25] S.-H. Hong, B.-K. Kim, and D.-S. Eom, “Localization algorithm in wireless sensor networks with network mobility,” IEEE Transactions on Consumer Electronics, vol.55, no.4, 2009.
[26] F. Dellaert, D. Fox, W. Burgard, and S. Thrun, “Monte Carlo localization for mobile robots,” in Proc. IEEE ICRA, 1999.
[27] A. Baggio and K. Langendoen, “Monte Carlo localization for mobile wireless sensor networks,” Ad Hoc Networks, vol.6, no.5, 2008.
[28] J.-P. Sheu, W.-K. Hu, and J.-C. Lin, “Distributed Localization Scheme for Mobile Sensor Networks,” IEEE Transactions on Mobile Computing, vol.9, no.4, 2010.
[29] S. Zhang, J. Cao, L.-J. Chen, and D. Chen, “Accurate and Energy-Efficient Range-Free Localization for Mobile Sensor Networks,” IEEE Transactions on Mobile Computing, vol.9, no.6, 2010.
[30] J. Yi, S. Yang, and H. Cha, “Multi-hop-based Monte Carlo Localization for Mobile Sensor Networks,” in Proc. IEEE SECON, 2007.
[31] S.-Y. Ni, Y.-C. Tseng, Y.-S. Chen, and J.-P. Sheu, “The Broadcast Storm Problem in a Mobile Ad Hoc Network,” in Proc. ACM MobiCom, 1999.
[32] J. Yi, J. Koo, and H. Cha, “A Localization Technique for Mobile Sensor Networks Using Archived Anchor Information,” in Proc. IEEE SECON, 2008.
[33] H.T. Friis, “A Note on a Simple Transmission Formula,” in Proc. IRE , 1946.
[34] E.M. Royer and C. Perkins., “Multicast operation of the ad-hoc on-demand distance vector routing protocol,” in Proc. ACM MobiCom, 1999.

指導教授

張貴雲(Guey-Yun Chang)

審核日期

2011-7-27

推文