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


下載電子全文限經由淡江IP使用) 
系統識別號 U0002-2505200520271800
中文論文名稱 無線行動感測網路上分散式無分割移動之通訊協定
英文論文名稱 A Distributed Partition-Free Lazy Movement Protocol for Mobile Sensor Networks
校院名稱 淡江大學
系所名稱(中) 資訊工程學系碩士班
系所名稱(英) Department of Computer Science and Information Engineering
學年度 93
學期 2
出版年 94
研究生中文姓名 蔡錦坤
研究生英文姓名 Jin-Kuen Tsai
學號 692191124
學位類別 碩士
語文別 中文
口試日期 2005-06-24
論文頁數 56頁
口試委員 指導教授-石貴平
委員-曾煜棋
委員-簡榮宏
委員-許健平
委員-石貴平
中文關鍵字 無線感測網路  行動感測網路  分散式無分割移動之通訊協定 
英文關鍵字 Connectivity  Coverage  Partition  Mobile Sensor 
學科別分類 學科別應用科學資訊工程
中文摘要 無線感測網路(Wireless Sensor Networks)會因為無線感測元件(Sensors)無法工作而使得網路產生分割(Partition),Partition將嚴重影響Coverage 的情況與Connectivity 的品質。因此,我們提出一個有效避免Partition 產生的分散式無分割移動之通訊協定(Distributed Partition-Free Lazy Movement Protocol,PLMP),PLMP 使用具移動性的感測裝置(Mobile Sensors)以避免Partition 的產生。
PLMP主要包括「Network Initialization Phase」和「Network Maintenance Phase」二個部分。在「Network Initialization Phase」中,整個行動感測網路(Mobile Sensor Network,MSN)將以Sink為主進行網路初始化的動作,這個部分將提供未來Mobile Sensors移動方向的依據。「Network Maintenance Phase」則是應用於網路可能產生Partition時,Mobile Sensors所需移動的位置與方向之計算。當Partition可能產生時,Connectivity 較差的Mobile Sensors將利用右手法則(Right Hand Rule)方式傳送封包並蒐集相關資訊,據以計算出一個考量到區域Coverage情況的移動位置,最後再移至該處維護網路的Connectivity。另外我們在效能分析中提出二個效能指標EIn與EIc分別判斷移動位置對於WSN中Coverage與Connectivity的影響。
PLMP 具有下列特色(1) 分散式的協定;(2)有效維護網路的Connectivity;(3)盡量減少Mobile Sensors 移動的時機與次數,以減少電量的消耗。實驗模擬的結果顯示出,分散式無分割移動之通訊協定較其他相關文獻所提出之協定更能避免Partition 的產生,使所有能夠工作的Mobile Sensors 可以貢獻他們的能力,以增加WSN 的存活時間。
英文摘要 According to the advancement of wireless technology, wireless sensor networks (WSNs) are widely adopted to many applications. Some partitions will appear in WSNs because some sensors are inactive. Partitions will reduce the coverage and weaken the connectivity of the WSN. We will provide a protocol (Distributed Partition-Free Lazy Movement Protocol, PLMP) which can prevent the appearance of partitions effectively. PLMP has some characteristics as follows:(1) It is distributed (2) It can maintain the connectivity of the WSN effectively (3)Less Number of movements.
論文目次 第 1 章 緒論 1
1.1 研究背景 1
1.2 研究動機 2
1.3 研究目的及方法 7
1.4 論文架構 9
第 2 章 背景知識 10
2.1 網路模型 10
2.2 Connectivity對感測任務影響之分析 11
2.3 網路拓樸結構對Coverage影響之分析 13
2.4 線性方程式 21
第 3 章 分散式無分割移動之通訊協定 23
3.1 Network Initialization Phase 23
3.2 Network Maintenance Phase 25
3.2.1 Stock Node Determination 25
3.2.2 Attach Nodes Discovery 28
3.2.3 Target Position Calculation 30
3.3 特殊情況處理 40
第 4 章 實驗與模擬 42
4.1 實驗環境 42
4.2 實驗結果 42
4.2.1 可與Sink連結的Mobile Sensors數量(ES) 42
4.2.2 移動次數 44
4.2.3 Mobile Sensors對MSN之貢獻(EIn) 45
4.2.4 整合EIn與EIc與的比較(EI) 47
4.2.5 結論 48
第 5 章 結論與未來研究方向 49
參考文獻 52
圖一 MSN中已形成一包含3個Mobile Sensors的Partition 4
圖二 相同數量的Mobile Sensors對MSN中感測結果的影響 12
圖三 三種網路拓樸對於Coverage與Connectivity的分析比較 15
圖四 S將計算與鄰居外心或中點距離標準差 19
圖五 直線L將平面區分為兩個區域R1與R2 21
圖六 網路初始化後,Mobile Sensors將可設定本身的Minimum Hop Count 25
圖七 MSN中已形成一包含3個Mobile Sensors的Partition 27
圖八 J收到I的封包後,以I為基準逆時針找到第一個鄰居K 28
圖九 Stock Node S將發起以Right Hand Rule為傳送方式的偵測封包 30
圖十 尋找Temporary Position 32
圖十一 任兩個Affecting Nodes彼此距離必須在2R內 33
圖十二 Protocol運作流程圖 34
圖十三 利用向量微調決定Stock Node移動位置 39
圖十四 特殊情況探討 41
圖十五 環境設定 42
圖十六 Non-Partition Sensors數的比較(ES) 43
圖十七 圖十六的放大圖 44
圖十八 移動次數的比較 45
圖十九 EIn的比較 46
圖二十 圖十九的放大圖 47
圖二十一 EI的比較 48
參考文獻 [1]. W.Zhang and G.Cao, “Optimizing tree reconfiguration for mobile target tracking in sensor networks,” in Proceedings of the IEEE International Conference on Computer Communications (INFOCOM), Mar. 2004, pp.2434–2445.
[2]. F. Ye, H. Luo, J. Cheng, S. Lu and L. Zhang, “A two-tier data dissemination model for large-scale wireless sensor networks,” in Proceedings of the 8th Annual International Conference on Mobile Computing and Networking
(MobiCom), Sep. 2002, pp. 148-159.
[3]. X. Ji, H. Zha, J. J. Metzner and G. Kesidis, “Dynamic cluster structure for object detection and tracking in wireless ad-hoc sensor networks,” in Proceedings of the IEEE International Conference on Communications (ICC), Jun. 2004, pp.3807-3811.
[4]. D. Tian and N. D. Georganas, “A coverage-preserving node scheduling scheme for large wireless sensor networks,” in Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, 2002, pp. 32–41.
[5]. F. Ye, G. Zhong, J. Cheng, S. Lu, and L. Zhang,“PEAS: a robust energy conserving protocol for long-lived sensor networks,” in Proceedings of the IEEE 23th International Conference on Distributed Computing Systems(ICDCS), May 2003, pp. 28–37.
[6]. Z. Zhou, S. Das, and H. Gupta, “Connected K-coverage problem in sensor networks,” in Proceedings of the 13th International Conference on Computer Communications and Networks, 2004, pp. 373–378.
[7]. S. Kumar, T. H. Lai, and J. Balogh, “On k-coverage in a mostly sleeping sensor network,” in Proceedings of the 10th annual international conference on Mobile computing and networking, 2004, pp. 144–158.
[8]. H. Gupta, S. R. Das, and Q. Gu, “Connected sensor cover : self-organization of sensor networks for efficient query execution,” in Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, 2003, pp.189–200.
[9]. H. Zhang and J. Hou, “Maintaining Sensing Coverage and Connectivity in Large Sensor Networks,” in NSF International Workshop on Theoretical and Algorithmic Aspects of Sensor, Ad Hoc Wireless, and Peer-to-Peer Networks,2004.
[10]. C. F. Hsin and M. Liu, “Network coverage using low duty-cycled sensors: random & coordinated sleep algorithms,” in Proceedings of the IEEE International Symposium on Information Processing in Sensor Networks (IPSN), Apr. 2004, pp. 433–442.
[11]. G. Xing, C. Lu, R. Pless, and J. O’Sullivan, “Co-Grid: an efficient coverage maintenance protocol for distributed sensor networks,” in Proceedings of the IEEE International Symposium on Information Processing in Sensor Networks(IPSN), Apr. 2004, pp. 414–423.
[12]. G. Wang, G. Cao, and T. LaPorta, “Movement-assisted sensor deployment,” in Proceedings of the IEEE International Conference on Computer Communications (INFOCOM), Mar. 2004, pp. 2469–2479.
[13]. N. Heo and P. Varshney, “A distributed self spreading algorithm for mobile wireless sensor networks,” in Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC), Mar. 2003, pp. 1597–1602.
[14]. P. Varshney and N. Heo, “An intelligent deployment and clustering algorithm for a distributed mobile sensor network,” in Proceedings of the IEEE International Conference on Systems, Man and Cybernetics, Oct. 2003, pp. 4576–4581.
[15]. T. Wong, T. Tsuchiya, and T. Kikuno, “A self-organizing technique for sensor placement in wireless micro-sensor networks,” in Proceedings of the 18th International Conference on Advanced Information Networking and Applications(AINA), 2004, pp. 78–83.
[16]. 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, Feb. 2004.
[17]. G. Wang, G. Cao, and T. LaPorta, “A bidding protocol for deploying mobile sensors,” in Proceedings of the 11th IEEE International Conference on Network Protocols(ICNP), Nov. 2003, pp. 315–324.
[18]. S. Ganeriwal, A. Kansal, and M. Srivastava, “Self aware actuation for fault repair in sensor networks,” in Proceedings of the 2004 IEEE International Conference on Robotics and Automation(ICRA), May 2004, pp. 5244–5249.
[19]. J. Hwang, D. Du, and E. Kusmierek, “Energy efficient organization of mobile sensor networks,” in Proceedings of the 2004 IEEE International Conference on Parallel Processing Workshops(ICPPW), Aug. 2004, pp. 84–91.
[20]. S. Zhou, M.-Y. Wu, and W. Shu, “Finding optimal placements for mobile sensors: wireless sensor network topology adjustment,” in Proceedings of the IEEE 6th Circuits and Systems Symposium on Emerging Technologies: Frontiers of Mobile and Wireless Communication(CAS), Jun. 2004, pp. 529–532.
[21]. A. Caruso, A. Urpi, S. Clessa, and S. De, “GPS Free Coordinate Assignment and Routing in Wireless Sensor Networks,” in Proceedings of the IEEE International Conference on Computer Communications (INFOCOM), Mar. 2005.
[22]. T. He, C. Huang, B. M. Blum, J. A. Stankovic, and T. Abdelzaher, “Range-free localization schemes for large scale sensor networks,” in Proceedings of the 9th Annual International Conference on Mobile Computing and Networking (MobiCom), 2003, pp. 81–95.
[23]. R. Iyengar and B. Sikdar, “Scalable and distributed GPS free positioning for sensor networks,” in Proceedings of the IEEE International Conference on Communications (ICC), May 2003, pp. 338–342.
[24]. K. Kalpakis, K. Dasgupta, and P. Namjoshi,“Efficient algorithms for maximum lifetime data gathering and aggregation in wireless sensor networks,” The International Journal of Computer and Telecommunications Networking, pp.697–716, Aug. 2003.
[25]. S. Meguerdichian, F. Koushanfar, M. Potkonjak, and M. Srivastava, “Coverage problems in wireless ad-hoc sensor networks,” in Proceedings of the IEEEInternational Conference on Computer Communications (INFOCOM), 2001, pp. 1380–1387.
[26]. H. Yang and B. Sikdar, “A protocol for tracking mobile targets using sensor networks,” in Proceedings of the IEEE International Workshop on Sensor Network Protocols and Applications (SNPA), May 2003, pp. 71–81.
[27]. K. Young-Bae and N. H. Vaidya, “Location-aided routing (LAR) in mobile ad hoc networks,” Wireless Networks, pp. 307–321, 2000.
論文使用權限
  • 同意紙本無償授權給館內讀者為學術之目的重製使用,於2005-07-13公開。
  • 同意授權瀏覽/列印電子全文服務,於2005-07-13起公開。


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