
系統識別號 
U00021607200713242300 
中文論文名稱

在無線感測網路中利用移動式定位裝置協助改善感測點位置精確度之路徑導引演算法 
英文論文名稱

Path Guiding Mechanisms for Improving Location Accuracy in WSNs 
校院名稱 
淡江大學 
系所名稱(中) 
資訊工程學系碩士班 
系所名稱(英) 
Department of Computer Science and Information Engineering 
學年度 
95 
學期 
2 
出版年 
96 
研究生中文姓名 
鄭人豪 
研究生英文姓名 
RenHau Cheng 
學號 
694190066 
學位類別 
碩士 
語文別 
英文 
口試日期 
20070609 
論文頁數 
55頁 
口試委員 
指導教授張志勇 委員陳裕賢 委員陳宗禧 委員王三元

中文關鍵字 
無線感測網路
定位
行動裝置
路徑導引
位置估算

英文關鍵字 
WSN
localization
mobile anchor
path guiding
location estimates

學科別分類 
學科別＞應用科學＞資訊工程

中文摘要 
在WSN(Wireless Sensor Network)中，Sensor定位是一個非常重要的議題，Sensors位置資訊越精準對於如物體追蹤，資料繞送，覆蓋區域偵測等問題越有幫助，在文獻中已有許多的方法被提出，以GPS(Global Positioning System )定位來提供精確位置資訊，其方式雖然簡單但是硬體成本過於昂貴。而近年來有人提出使用具有精確位置資訊(如裝設全球定位系統GPS)的 Mobile Anchor移動以提供或改善其他Sensors位置資訊的精確度。但是未針對Mobile Anchor的移動方式加以討論，本論文提出一個分散式路徑Guiding 技術, 使Mobile Anchor 依現有Static Sensors 的位置精準程度作有效率的移動，實驗顯示，本論文所提的方法不僅可使Static Sensors快速改善定位的精準度，亦可最佳化Mobile Anchor有效移動，使其單位移動量所改善的位置精準度最大，得到的利益最多。 
英文摘要 
In the most proposed rangefree algorithms, nodes estimate their location using the geometric constraints imposed by the location of mobile anchor. However, there is no discussion on how the mobile anchor moves so that all sensor nodes can obtain the maximal location accuracies under the constraints of time for localization or the remaining energy of the robot. This paper assumes that traditional rangefree algorithms have been executed for a certain time period and the deployed sensors are with different location accuracies. We propose path guiding mechanisms that sensor nodes cooperatively guide the mobile anchor moving along an efficient path which can maximize the improvement of location accuracies or minimize the accuracy differences for all sensor nodes in a given WSN. Experimental study reveals that the proposed path guiding mechanisms effectively guide the mobile anchor moving along the efficient path and thereby saves time and energy consumptions for improving or balancing the location accuracies of all sensor nodes. 
論文目次 
List of Contents
List of Contents I
List of Figures II
I.Introduction 1
II.Related Work 4
III.Network Environment & Problem Statement 7
3.1 Network Environment 7
3.2 Problem Statement 7
3.3 Problem formation 9
IV.The Guiding Mechanisms 12
4.1 Identifying Promising Region Phase (IPRP) 12
4.2 Weighting Phase (WP) 14
4.3 Beacon Locations Selection Phase (BLSP) 17
4.3.1 BenefitBased Selection Scheme 18
4.3.2 DistanceBased Selection Scheme 20
4.3.3 AccuracyBalancing Based Selection Scheme 21
4.4 Path Construction Phase (PCP) 26
V.Performance Study 29
5.1 The Impact of Network Density and Localization Time on Mean Position Error 29
5.2 The ratio of Localization Accuracies and Energy Consumption 31
5.3 The Mean Error and threshold 33
5.4 Performance Comparison in terms of Balance Index 34
5.4 A Look on the Physical Scenarios 35
VI.Conclusions 39
REFERENCES 40
附錄英文論文 42
List of Figures
Figure 1: An example that illustrates the calculation of new estimate region ERs,t’ of sensor s when it receives a beacon b(xm, ym)t’ from mobile anchor m. 8
Figure 2: Mobile anchor moves along path p1 and broadcasts a beacon at location b will contribute more benefits to the localization than moves along path p2 and broadcasts a beacon at location c. 10
Figure 3: The promising region of sensor s can be determined by the constraint that the mobile anchor is located with the communication range of sensor s. 13
Figure 4: The promising region of sensor s excludes the subregion where the rangeconstraint contains the estimate region of sensor s. 14
Figure 5: (a)The gray area represents the possible locations that mobile anchor m can communicate with sensor s. (b)The new estimate region ERs,t’, denoted by the dotted rectangle, is evaluated according to the new rangeconstraint. 16
Figure 6: Mobile anchor broadcasts a beacon at grid g(x, y) so that a new estimate region ERs,t’ of sensor s has been formed. Let the ERs,t’ is sized with m×n. The helpless region to ERs,t’ will be the gray rectangle. 18
Figure 7: An example of applying the BenefitBased Grid Selection Scheme to select grids for broadcasting beacons. 20
Figure 8: (a) Grid g(2, 4) is selected as a beacon location in . (b) Broadcasting a beacon at grid g(2, 4) will form a new ER which is represented by the dotted rectangle. (c) The shadow region represents the new HLR. (d) Grid g(6, 3) is located outside the HLR and hence is selected for being a beacon location. (e)The shadow region represents the new ER after selecting grid g(6, 3) as a beacon location. (f)The SEBA procedure is completed when is covered by HLR set. 26
Figure 9: An example for illustrating the PCP phase. (a)The edge connecting g(xm, ym) and a is constructed. (b) Another edge that connects grids a and b is constructed. 27
Figure 10: The impact of network densities and time spent for localization on the position error. 31
Figure 11: BBPGM, DBPGM and ABPGM achieve higher localization efficiency than the other two mechanisms under the energy constraint. 33
Figure 12: The impact of threshold values on the anchor’s energy consumption as well as the mean position error. 34
Figure 13: DBPGM and ABPGM achieves higher balance of the location accuracies of all sensors under the constraint of energy consumption. 35
Figure 14: The snapshot of the simulation scenario. 37
Figure 15: The path and the beacon locations by applying the proposed BBPGM,DBPGM and ABPGM. 37 
參考文獻 
[1]D. Niculescu, and B. Nath, “Adhoc positioning system (APS) using AOA,” Proc. of IEEE Infocom, 2003.
[2]P. Bahl, and V. N. Padmanabhan, “RADAR: an inbuilding RFbased user location and tracking system,” Proc. of IEEE Infocom, 2000.
[3]K. Chintalapudi, A. Dhariwal, R. Govindan, and G. Sukhatme, “Adhoc localization using ranging and sectoring,” Proc. of IEEE Infocom, 2004.
[4]Y. Shang, W. Ruml, and Y. Zhang, “Improved MDSbased localization,” Proc. of IEEE Infocom, 2004.
[5]T. He, C. Huang, B. Lum, J. Stankovic, and T. Adelzaher, “Rangefree localization schemes for large scale sensor networks,” Proc. of ACM MobiCom, 2003.
[6]Chong Liu ,Kui Wu, and Tian HeComputer, “Sensor Localization with Ring Overlapping Based on Comparison of Received Signal Strength Indicator,” Proc. of IEEE MASS, 2004.
[7]Vijayanth Vivekanandan, and Vincent Wong, “Concentric AnchorBeacons (CAB) Localization for Wireless Sensor Networks,“ Proc. of IEEE ICC, 2006.
[8]Srinath T V, “Localization in Resource Constrained Sensor Networks using a Mobile Beacon with InRanging,” Proc. of IEEE WOCN, 2006.
[9]Jang Ping Sheu, Jian Ming Li, and C. S. Hsu, “A Distributed Location Estimating Algorithm for Wireless Sensor Networks,” Proc. of IEEE SUTC, 2006.
[10]A. Galstyan, B. Krishnamachari, and K. Lerman, ”Distributed online localization in sensor networks using a moving target,” Proc. of IEEE IPSN, 2004.
[11]Yongguo Mei, YungHsiang Lu, Y. Charlie Hu, and C.S. George Lee, "Deployment Strategy for Mobile Robots with Energy and Timing Constraints," Proc. of IEEE ICRA, 2005.
[12]X. Zeng, R. Bagrodia and M. Gerla, “GloMoSim: a library for parallel simulation of largescale wireless networks,” Proc. of PADS, 1998.

論文使用權限 
同意紙本無償授權給館內讀者為學術之目的重製使用，於20120718公開。同意授權瀏覽/列印電子全文服務，於20120718起公開。 


