淡江大學覺生紀念圖書館 (TKU Library)
進階搜尋


下載電子全文限經由淡江IP使用) 
系統識別號 U0002-1207200614242000
中文論文名稱 應用於移動式感測網路之空洞正規化協定
英文論文名稱 HONOR: HOle NORmalization Protocol for Mobile Sensor Networks
校院名稱 淡江大學
系所名稱(中) 資訊工程學系碩士班
系所名稱(英) Department of Computer Science and Information Engineering
學年度 94
學期 2
出版年 95
研究生中文姓名 許仕昀
研究生英文姓名 Shih-Yun Hsu
學號 693190117
學位類別 碩士
語文別 中文
口試日期 2006-06-13
論文頁數 91頁
口試委員 指導教授-張志勇
委員-曾煜棋
委員-簡榮宏
委員-許健平
委員-張志勇
中文關鍵字 空洞正規化  移動式感測器  空洞修復  空洞巡邏  無線感測網路 
英文關鍵字 Hole normalization  Mobile sensor  Hole patrol  Hole redeployment  Sensor Networks 
學科別分類 學科別應用科學資訊工程
中文摘要 在Wireless Sensor Networks (WSNs)環境之中,由於佈點不均、環境外力影響或電量耗盡等因素而產生大型空洞,影響感應的精確性或通訊的效率。近年來有許多研究提出以機器人攜帶static sensor去填補空洞或是以mobile sensor來巡邏空洞的區域,這兩種作法雖可分別達到spatial及temporal full coverage。然而,形狀不規則的空洞,將導致機器人再佈建或是mobile sensor的巡邏效率不彰。本論文研發一新穎的機制,在mobile sensor networks的環境中,針對空洞進行正規化,透過mobile sensor nodes的少許移動,使不規則的空洞轉變成較為規則且為凸狀的空洞,以提升機器人再佈點或mobile sensor巡邏之效率,進而達到節省電量及縮短delay time的目的。
英文摘要 In Wireless Sensor Networks (WSNs), a big hole is formed due to the non-uniform deployment, node failure and movement of animals’ residence or fierce wind blowing, resulting a region without sensor working for sensing and communication tasks. The existence of big hole will reduce both the accuracy of the environmental monitoring and the efficiency of sensing and communications. Recently, many studies proposed mechanisms to detach a robot that loads up static sensors to heal the hole and maintain the spatial full coverage. Some other studies utilized mobile sensors to patrol the hole, maintaining the temporal full coverage. However, an irregular hole will result in the redeployment and patrol inefficiency. This thesis proposes a novel mechanism to regularize a big irregular hole for a mobile WSN. Mobile sensors who detect the big hole cooperate with each other to change the shape of the irregular hole to a convex and regular one in a distributed manner. The robot’s redeployment and the mobile sensors’ patrol are therefore can be more efficient. Simulation results reveal that applying the proposed HONOR mechanism saves power consumption and delay time for the robot’s redeployment and the mobile sensors’ patrol.
論文目次 目錄
目錄 i
圖目錄 iii
表目錄 v
第一章、緒論 1
第二章、環境假設及動機 5
2.1 Network Model 5
2.2 空洞正規化之動機 7
2.3 Problem Statement 12
第三章、空洞規則性探討 13
3.1 不規則與規則空洞 13
3.2 空洞規則程度 14
第四章、Hole Normalization protocol (HONOR) 22
4.1 Basic Concept of HONOR protocol 22
4.2 HONOR protocol細節論述 26
4.2.1 Negotiation phase 26
4.2.2 Calculation phase 36
4.2.2 Movement phase 48
4.2.3 HONOR protocol Enhancement 50
第五章、HONOR protocol分析 60
5.1 mobile sensor最大移動步數 60
5.2 總移動步數 62
5.2.1 最大總移動步數 (worst case) 64
5.2.2 最小總移動步數 (best case) 67
第六章、模擬實驗 71
6.1 Simulation Model 71
6.2 實驗結果 72
第六章、結論 81
參考文獻 82

圖目錄
圖(一): 整體網路形同以六角形切割,在每個六角形中均存在
一mobile sensor。 7
圖(二): 機器人針對不規則空洞進行巡邏的各種策略,不規則
的空洞對各種巡邏策略均造成效率不彰。 10
圖(三): 採用研究[14]的方法進行不規則空洞的填補,會造成
網路有多餘的sensor nodes及大量的封包交換。 11
圖(四): 規則及不規則空洞。 14
圖(五): hole cell之weight的計算方式。 14
圖(六): 計算大型空洞之總weight值。 16
圖(七): 正規化程度的計算。 19
圖(八): 不規則空洞與規則空洞之正規化程度。 21
圖(九): 將空洞正規化的簡易示意圖。 23
圖(十): HONOR protocol簡易示意圖。 23
圖(十一): HONOR protocol大致的運作流程。 25
圖(十二): 定義Border node以及Hole boundary cell。 26
圖(十三): 定義突出以及凹陷之區域。 29
圖(十四): 三種不同的cases討論來表示計算hole boundary cell
之BN至多只需要與之相鄰三步的border node交換資訊
即可。 31
圖(十五): Negotiation phase中所使用的鄰近節點與鄰近空洞表
示法。 33
圖(十六): X取得三步鄰居資訊之實例。 35
圖(十七): Neighboring Hole Boundary Cell Mapping演算法。 38
圖(十八): Border node之HN值必須大於1才能移動以進行空洞填
補。 43
圖(十九): 不同HN的border node在Movement phase的priority對
應。 44
圖(二十): 經過C.Rule 1正規化後,仍然未正規化完全。 44
圖(二十一):Concave node之HN值為4以上時才符合C.Rule 2。 46
圖(二十二):Calculation phase C.Rule 2。 47
圖(二十三):Movement phase的時槽以及priority安排。 50
圖(二十四):不使用Delay機制所帶來的振盪效應。 51
圖(二十五):Delay 1造成將正規化時間延長。 52
圖(二十六):Delay 2之方向定義。 53
圖(二十七):整個Movement phase 之priority示意圖。 55
圖(二十八):border node被孤立的狀況。 56
圖(二十九):HONOR protocol無法停止的情況。 57
圖(三十): 空洞對於機器人巡邏的影響。 59
圖(三十一):觀察不規則空洞以及正規化後而形成的規則空洞,推
導mobile sensor可能的最大移動步數。 61
圖(三十二):從大型規則空洞變形成大型不規則空洞,探討正規化
一步規則空洞需要mobile sensors移動的總步數。 63
圖(三十三):最大總移動步數演算法。 65
圖(三十四):以分散的方式從多處同時進行空洞變形。 68
圖(三十五):最大總移動步數演算法。 69
圖(三十六):大型空洞正規化前以及使用各正規化方式所達到的正
規化程度。 73
圖(三十七):mobile sensors針對不同場景及空洞大小所需移動的
總步數。 74
圖(三十八):使用HONOR protocol將大型空洞正規化所需的時間。 75
圖(三十九):於各個不同大小場景中,mobile sensor於正規化時移
動的最大步數。 76
圖(四十): 機器人以規則行走方式巡邏空洞所需消耗的電量。 77
圖(四十一):場景越大時,HONOR所消耗的電量將比未正規化來的
少。 78
圖(四十二):機器人巡邏數個round時所消耗的電量。 80

表目錄
表(一):border node記錄其中一邊三步內hole boundary cell及
sensor nodes 分佈狀況。 37
表(二):各符號定義。 41
表(三):模擬實驗參數。 71


參考文獻 [1] I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, “Wireless sensor network: a survey,” Computer Networks, Vol. 38, pp. 393-422, 2002.

[2] C. Y. Chong and S. P. Kumar, “Sensor network: Evolution, opportunities, and challenges,” Proceeding of the IEEE, Vol. 91, No. 8, pp. 1247-1256, Aug. 2003.

[3] D. Estrin, R. Govindan, J. Heidemann, and S. Kumar, “Next century challenges: Scalable coordination in sensor networks,” IEEE/ACM Mobicom’99, pp. 263-270, Aug. 1999.

[4] X. Liu, H. Hou, J. Yang, H. Yu, and H.Hu, “Coverage and Energy Information Gathering Protocol in Wireless Sensor Networks,” IEEE Parallel and Distributed Computing, Applications and Technologies (PDCAT) 2005, pp. 649-654, Dec. 2005.

[5] A. Ghosh, and T. Givargis, “LORD: A Localized, Reactive and Distributed Protocol for Node Scheduling in Wireless Sensor Networks,” IEEE Design, Automation and Test in Europe 2005, vol. 1, pp. 190-195, March 2005.

[6] M. A. Batalin and G. S. Sukhatme, “Coverage, Exploration and Deployment by a Mobile Robot and Communication Network,” Proceedings of the International Workshop on Information Processing in Sensor Network (IPSN), Palo Alto, pp. 376-391, Apr. 2003.

[7] M. A. Batalin, G. S. Sukhatme and M. Hattig, “Mobile Robot Navigation using a Sensor Network,” Proceedings of the IEEE International Conference on Robotics & Automation (ICRA), New Orleans, LA, pp. 636-642, April 2004.

[8] M. A. Batalin and G. S. Sukhatme, “Efficient Exploration without Localization,” in IEEE International Conference on Robotics and Automation (ICRA), Taipei, Taiwan, pp. 2714–2719, May 2003.

[9] G. Wang, G. Cao and T. La Porta, “A Bidding Protocol for Deploying Mobile Sensors,” The 11th IEEE International Conference on Network Protocol, pp. 315-324, Nov. 2003.

[10] J. Hwang, D. H. C. Du and E. Kusmierek, “Energy Efficient Organization of Mobile Sensor Networks,” IEEE International Conference on Parallel Processing Workshop, pp. 84-91, 2004.

[11] G. Wang, G. Cao, T. L. Porta, and W. Zhang, “Sensor Relocation in Mobile Sensor Networks,” IEEE INFOCOM, vol. 4, pp. 2302-2312, March 2005.

[12] Chih-Yung Chang, Chen-Chi Hsieh, and Shih-Chieh Lee, “Obstacle-Free Robot Deployment and Repair Algorithms for Wireless Sensor Networks” Wireless, Ad-hoc, and Sensor Networks (WASN), 2005.

[13] Y. Zou and K. Chakrabarty, “Sensor Deployment and Target Localization in Distributed Sensor Networks,” ACM Transactions on Embedded Computing Systems (TECS), vol. 3, pp. 61-91, 2004.

[14] Niaoning Shan and Jindong Tan, “Mobile Sensor Deployment for a Dynamic Cluster-based Target Tracking Sensor Network,” IEEE/RSJ International Conference on Intelligent Robots and Systems, 2005

[15] B. Liu, P. Brass, and O. Dousse, “Mobility Improves Coverage of Sensor Networks,” International Symposium on Mobile Ad Hoc Networking & Computing (MobiHoc), pp. 300-308, 2005.


[16] Miklós Maróti, Branislav Kusy, Gyula Simon, and Ákos Lédeczi, “The flooding time synchronization protocol,” Proceedings of the 2nd ACM International Conference on Embedded Networked Sensor Systems (SenSys), pp. 39-49, November 2004.

[17] Qun Li and Daniela Rus, “Global Clock Synchronization in Sensor Networks,” IEEE Transactions on Computers, Vol. 55, Issue 2, pp. 214-226, Feb. 2006.

[18] Hongyi Wu, Chong Wang, and Nian-Feng Tzeng, “Novel Self-Configurable Positioning Technique for Multihop Wireless Networks,” IEEE/ACM Transactions on Networking, Vol. 13, No. 3, June 2005.

[19] Antonio Caruso, Stefano Chessa, Swades De, and Alessandro Urpi, “GPS Free Coordinate Assignment and Routing in Wireless Sensor Networks,” IEEE INFOCOM, Vol. 1, pp. 150-160, March 2005.

[20] Nissanka B. Priyantha, Hari Balakrishnan, Erik D. Demaine, and Seth Teller, “Mobile-Assisted Localization in Wireless Sensor Networks,” IEEE INFOCOM, Vol. 1, pp. 172-183, March 2005.

[21] nesC: A Programming Language for Deeply Networked Systems http://nescc.sourceforge.net/

[22] http://www.tinyos.net/



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


  • 若您有任何疑問,請與我們聯絡!
    圖書館: 請來電 (02)2621-5656 轉 2281 或 來信