跳到主要內容

臺灣博碩士論文加值系統

(44.200.169.3) 您好!臺灣時間:2022/12/04 10:43
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:張時瑜
研究生(外文):Shih-Yu Chang
論文名稱:在具障礙物的無線感測網路環境下中繼節點佈建方法之研究
論文名稱(外文):Relay Node Deployment in Wireless Sensor Networks with Obstacles
指導教授:陳永昇陳永昇引用關係
口試委員:鄭欣明湯政仁
口試日期:2015-07-16
學位類別:碩士
校院名稱:國立臺北教育大學
系所名稱:資訊科學系碩士班
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2015
畢業學年度:103
語文別:中文
論文頁數:38
中文關鍵詞:無線感測網路中繼節點佈建演算法最短路徑演算法
外文關鍵詞:wireless sensor networkrelay nodedeploymentshortest path algorithm
相關次數:
  • 被引用被引用:0
  • 點閱點閱:117
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
在無線感測網路(wireless sensor network, WSN)環境中,感測器(Sensor)與控制中心(Control Center或稱Sink)的距離往往大於訊號的傳送範圍,因此需要在兩者之間佈建中繼節點(relay node),來轉送資料,達到傳遞資料的目的,然而,在有障礙物的無線感測網路環境中,這個問題會更加複雜。本研究針對在有障礙物的無線感測網路環境中,佈建中繼節點的方法進行研究與分析,首先將整個場域格點化,每一個格點僅能包含一個節點(即感測器、中繼節點或控制中心),然後使用最短路徑演算法,在感測器與控制中心之間找出最短路徑,再以訊號強度範圍為基礎,以適當傳輸距離沿著路徑佈建中繼節點,期間並針對每一次的佈建進行避障演算法來繞過障礙物。我們運用不同的最短路徑演算法來進行設計,並實作出一個網頁式的自動化中繼節點佈建系統來進行模擬與研究,由實驗結果顯示,所設計的系統可以在有障礙物的無線感測網路中,有效的佈建中繼節點,並最佳化中繼節點的佈建數量,實驗數據顯示運用Jump Point最短路徑演算法得出的佈建結果,其平均中繼節點距離最短,而使用A*最短路徑演算法得出的佈建結果,其平均中繼節點數最少。
In a wireless sensor network, usually the control center (or called sink) is out of the communication range of the sensor node, and cannot directly receive the data sent from the sensor node. In such a case, relay nodes are used to forward the data so that the control center can receive the data from the sensor node. However, this problem becomes more complicated for WSNs with obstacles. This study investigates the deployment schemes of the relay nodes in WSNs with obstacles. First, the target area is divided into square grids, in which each grid cell has exactly one node (a sensor node, a relay node, or the control center). The minimum shortest path algorithm is applied to identify the shortest path from the sensor node to the control center. Then, relay nodes are deployed along the shortest path by computing the communication range. Meanwhile, a proposed obstacle avoidance algorithm is used to ensure that the communication between two consecutive relay nodes is not obstructed by the obstacles. Different minimum shortest path algorithms are considered in the proposed scheme. Besides, a web based automatic relay node deployment system was developed to verify the proposed scheme. Our experiments show that the developed system can effectively deploy the relay nodes while minimizing the number of relay nodes. Experiment results also show that the deployment based on Jump Point shortest path algorithm has the shortest average distance between two consecutive relay nodes; and he deployment based on A* shortest path algorithm has the minimum number of relay nodes.
目錄
摘要 i
Abstract ii
目錄 iii
表目錄 v
圖目錄 vi
第1章 緒論 1
1.1 前言 1
1.2 研究動機與目的 2
1.3 文章架構 3
第2章 相關技術研究與文獻探討 4
2.1 定位問題 4
2.2 覆蓋率最佳化問題 5
2.3 中繼節點的佈建問題 6
2.4 最短路徑演算法 7
2.5 ZigBee 9
2.6 HTML5 10
第3章 中繼節點佈建之方法與系統開發 11
3.1 環境描述 11
3.2 問題描述 13
3.3 系統開發流程 15
3.4 佈建環境建置階段 16
3.5 格點化與節點佈建放置階段 19
3.6 路徑演算階段 21
3.7 結果呈現 25

第4章 研究結果與分析討論 29
4.1 A*演算法 30
4.2 Depth First演算法 31
4.3 Breadth First演算法 32
4.4 Dijkstra演算法 33
4.5 Jump Point演算法 34
4.6 綜合分析討論 35
第5章 結論與未來展望 36
5.1 結論 36
5.2 未來展望 36
參考文獻 37


表目錄
表 4 1 A* 結果數據表 30
表 4 2 DEPTH FIRST結果數據表 31
表 4 3 BREADTH FIRST結果數據表 32
表 4 4 DIJKSTRA結果數據表 33
表 4 5 JUMP POINT結果數據圖 34
表 4 6綜合分析數據表 35

圖目錄
圖 3 1中繼節點傳遞訊號示意圖 11
圖 3 2環境描述示意圖 12
圖 3 3格點化環境示意圖 13
圖 3 4本研究之設計流程圖 15
圖 3 5初始化介面圖 16
圖 3 6台灣中油煉油廠廠區圖 18
圖 3 7點物件放置圖 20
圖 3 8路徑運算階段 21
圖 3 9訊號穿過障礙物的情況 22
圖 3 10完整的路徑 23
圖 3 11避障演算法判斷前 23
圖 3-12避障演算法判斷後 23
圖 3-13 中繼節點的佈建順序 24
圖 3-14模擬結果顯示圖 25
圖 3-15感測器位置顯示方法 25
圖 3-16路徑顯示方式 26
圖 3-17修改中繼節點的位置 27
圖 3-18中繼節點修改後模擬圖 27
圖 4-1用來分析的佈建模擬圖 29
圖 4-2 A*模擬結果圖 30
圖 4-3 DEPTH FIRST模擬結果圖 31
圖 4-4 BREADTH FIRST模擬結果圖 32
圖 4-5 DIJKSTRA模擬結果圖 33
圖 4-6 JUMP POINT模擬結果圖 34

[1]. 鍾欣儒,無線感測網路覆蓋率最佳化之研究,碩士論文,中國文化大學數位電機科技研究所,民國99年。
[2]. 張宜穎,無線人體區域感測網路之中繼節點佈建方法,碩士論文,國立清華大學資訊工程研究所,民國99年。
[3]. 楊嵐智,用於K夾角覆蓋問題之感測節點佈建演算法,碩士論文,國立清華大學資訊工程演究所,民國98年。
[4]. 王友群,行動無線感測網路下的佈建、派遣、與封包排程之議題研究,博士論文,國立交通大學資訊工程研究所,民國95年。
[5]. 吳俊賢,無線感測網路之佈建策略,博士論文,國立清華大學資訊工程研究所,民國99年。
[6]. 林均翰,無線感測網路中保證系統覆蓋率與運作時間之佈建技術,博士論文,國立清華大學資訊工程研究所,民國99年。
[7]. 吳為勛,利用分群虛擬力佈建行動感測網路,碩士論文,國立中正大學資訊管理研究所,民國95年。
[8]. 黃振愷,以變動長度多目標基因演算法為基礎解決多重限制異質性無線傳輸設備佈建之方法,碩士論文,國立中山大學資訊工程研究所,民國97年。
[9]. 劉蓓縝,無線感測網路中繼節點佈建方法之研發-以室內環境為例,碩士論文,國立交通大學電機學院IC設計產業研發研究所,民國96年。
[10] Bin Hao, Jian Tang, & Guoliang Xue. “Fault-tolerant relay node placement in wireless sensor networks: formulation and approximation, ” High Performance Switching and Routing, 2004. HPSR. 2004 Workshop on, 246-250, 2004.
[11] Y.T. Hou, Yi Shi, H.D. Sherali, and S.F. Midkiff, “On energy provisioning and relay node placement for wireless sensor networks,” Wireless Communications, IEEE Transactions Vol. 4, No. 5, pp. 2579-2590, Sept 2005.
[12] Errol L. Lloyd and Guoliang Xuey, “Relay Node Placement in Wireless Sensor Networks,” Computers, IEEE Transactions, Vol. 56, No.1, pp.134-138, Jan 2007.
[13] Guangjie Han, et al., “Localization algorithms of wireless sensor networks: a survey,” Telecommunication Systems, Vol. 52, No. 4, pp. 2419-2436, April 2013.
[14] J. P. Sheu, P. C. Chen, 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, pp. 1110-1123, September 2008.
[15]JP Sheu, WK Hu, and JC Lin, “Distributed Localization Scheme for Mobile Sensor Networks, ”Mobile Computing, IEEE Transactions,Vol.9,pp. 516 – 526,April 2010.
[16] L. Doherty, K. S. J. Pister, and L. E. Ghaoui,“Convex Position Estimation in Wireless Sensor Networks,” Proceedings of the 20th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM 2001), vol. 3, pp. 1655-1663, April 2001.
[17] Taeyoung Kim, et al., "Anchor-node-based distributed localization with error correction in wireless sensor networks," International Journal of Distributed Sensor Networks, Volume 2012, Article ID 975147, 2012.
[18] Harabor, Daniel Damir, and Alban Grastien. "Online Graph Pruning for Pathfinding On Grid Maps," Association for the Advancement of Artificial Intelligence. 2011.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關期刊