無線感測網路分散式阻障覆蓋最佳化規劃

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：20

、訪客IP：18.226.82.220

姓名

秦承鴻(Cheng-Hung Chin) 查詢紙本館藏

畢業系所

資訊工程學系

論文名稱

無線感測網路分散式阻障覆蓋最佳化規劃
(Distributed Barrier Coverage Optimization for Wireless Sensor Networks)

相關論文

★ 以IEEE 802.11為基礎行動隨意無線網路之混合式省電通訊協定	★ 以范諾圖為基礎的對等式網路虛擬環境相鄰節點一致性研究
★ 行動隨意網路可調適及可延展之位置服務協定	★ 同儕式網路虛擬環境高效率互動範圍群播
★ 巨量多人線上遊戲之同儕網路互動範圍語音交談	★ 基於范諾圖之同儕式網路虛擬環境狀態管理
★ 利用多變量分析之多人線上遊戲信任使用者選擇	★ 無位置資訊無線感測網路之覆蓋及連通維持
★ 同儕網路虛擬環境3D串流同儕選擇策略	★ 一個使用802.11與RFID技術的無所不在導覽系統U-Guide之設計與實作
★ 同儕式三維資料串流	★ IM Finder: 透過即時通訊網路線上使用者找尋解答
★ 無位置資訊無線感測網路自走車有向天線導航與協調演算法	★ 多匯點無線感測網路省能及流量分散事件輪廓追蹤
★ 頻寬感知同儕式3D串流	★ 無線感測網路旋轉指向天線定位法

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

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

摘要(中)

無線感測網路(wireless sensor network, WSN)可以在一個帶狀監控區域內形成一個阻障覆蓋(barrier coverage)，以偵測入侵者穿越監控區域事件的發生。而建構阻障覆蓋需要同時考慮覆蓋品質及建構成本。在覆蓋品質方面主要考慮的是：穿越偵測程度(degree) k 及每一對相鄰感測器所形成之偵測線段的偵測機率。在建構成本方面主要考慮的是：啟動的感測器個數及建構過程中所傳遞的訊息量。現有的研究大都以集中式(centralized)建構方法嘗試達成高覆蓋品質或低建構成本。本研究目的為利用分散式(distributed)的建構方法，在給定穿越偵測程度k值的條件下，盡可能地使用最少的感測器在WSN上建構阻障覆蓋，使得每一對相鄰感測器的偵測機率皆在門檻值(λ)之上。我們提出利用地理路由(geographical routing, GR)的路徑建構概念來建構阻障覆蓋的方法，由來源端節點(source node)開始發送建構阻障覆蓋的訊息，在經過一連串的中間節點之後達到目的端節點(destination node)，訊息傳送中的每個節點根據不同的選擇基準(角度、距離等)來選擇barrier中的下一個節點，當訊息抵達目的端時即構成阻障覆蓋。我們針對四種不同的地理路由(greedy routing scheme, most forward within radius routing, compass routing, random select routing)的路徑建構概念求得的阻障覆蓋與利用centralized algorithm求得的最佳覆蓋節點個數進行比較。實驗結果顯示greedy routing與most forward within radius routing在高偵測機率門檻值(λ)的情況下，相當逼近於最佳的節點個數且所產生的訊息量也最低。

摘要(英)

Some recent research uses a wireless sensor network (WSN) to form barrier coverage to detect intruders crossing a belt-shaped region. Constructing barrier coverage should consider the barrier coverage quality and the construction cost. In point of barrier coverage quality, we should consider the detection degree and the detection probability of the detection line between every pair of neighboring nodes. In point of construction cost, we should consider the number of delivered messages and the number of active nodes. Most research uses centralized algorithm to construct barrier coverage with high coverage quality and low construction cost. In this thesis, we study the optimization problem about how to construct in a distributed manner the barrier coverage with the detection degree of k and the detection quality larger than a threshold λ by using the minimized number of sensor nodes. Four distribution algorithms are proposed on the basis of different geographical routing schemes, which are the greedy routing, the most forward within radius routing, the compass routing, and the random select routing. Simulation experiments are conducted for evaluating the performance of the proposed algorithms in terms of the number of active sensor nodes and the number of delivered messages. The simulation results show the algorithm based on the greedy routing and the algorithm based on the most forward within radius routing both approach the bound of the optimal number of active sensor nodes, derived by a centralized optimization algorithm, and use the minimum number of delivered messages among the four algorithms.

關鍵字(中)

★ 無線感測網路
★ 阻障覆蓋
★ 地理路由
★ 最佳化

關鍵字(英)

論文目次

中文摘要 i
目錄 iii
圖目錄 iv
一、緒論 1
二、相關研究 4
2.1 阻障覆蓋(Barrier Coverage) 4
2.1.1 集中式建構方法 6
2.1.2 非集中式建構方法 11
2.2 地理路由路徑建構概念 14
三、網路模型與問題描述 16
3.1 網路模型 16
3.2 機率感測模型 18
3.3 問題描述 20
四、提出方法 21
4.1 假設 21
4.2 協定設計 22
4.2.1 主要概念 22
4.2.2 區域變數及訊息結構 23
4.2.3 演算法設計 24
五、實驗模擬 27
5.1 環境設定 27
5.2 模擬度量 28
5.3 效能評估 29
六、結論 34
參考文獻 35

參考文獻

[1] Ahmed, N., Kanhere, S. S., & Jha, S. (2005). Probabilistic coverage in wireless sensor networks. Local Computer Networks, 2005. 30th Anniversary. the IEEE Conference on, 8 pp.-681.
[2] Ai Chen, Kumar, S., & Lai, T. H. (2010). Local barrier coverage in wireless sensor networks. Mobile Computing, IEEE Transactions on, 9(4), 491-504.
[3] A. Goldberg and R. Tarjan, “Solving minimum-cost flow problems by successive approximation,” in STOC ’87: Proceedings of the nineteenth annual ACM symposium on Theory of computing. New York, NY, USA:ACM, 1987, pp. 7–18.
[4] Chen, A., Lai, T. H., & Xuan, D. (2008). Measuring and guaranteeing quality of barrier-coverage in wireless sensor networks. Proceedings of the 9th ACM International Symposium on Mobile Ad Hoc Networking and Computing, 421-430.
[5] Finn, G. G. (1987). Routing and Addressing Problems in Large Metropolitan-Scale Internetworks, Technical Report ISI/RR-87-180, ISI, 1987.
[6] Gage, D. W. (1992). Command Control for Many-Robot Systems, Proc. of the Nineteenth Annual AUVS Technical Symposium (AUVS-92), 1992.
[7] Guanqun Yang, & Daji Qiao. (2009). Barrier information coverage with wireless sensors. INFOCOM 2009, IEEE, 918-926.
[8] He, J., & Shi, H. (2010). Finding barriers with minimum number of sensors in wireless sensor networks. Communications (ICC), 2010 IEEE International Conference on, 1-5.
[9] Junkun Li, Jiming Chen, & Lai, T. H. (2012). Energy-efficient intrusion detection with a barrier of probabilistic sensors. INFOCOM, 2012 Proceedings IEEE, 118-126.
[10] Kranakis, E., Singh, H., & Urrutia, J. (1999). Compass routing on geometric networks. In Proc. 11 Th Canadian Conference on Computational Geometry,
[11] Kumar, S., Lai, T. H., & Arora, A. (2005). Barrier coverage with wireless sensors. Proceedings of the 11th Annual International Conference on Mobile Computing and Networking, 284-298.
[12] Lai, Y. L., & Jiang, J. R. (2011). Sink-connected barrier coverage optimization for wireless sensor networks. ICWMC 2011, the Seventh International Conference on Wireless and Mobile Communications, 198-203.
[13] Lemmon, C., Siu Man Lui, & Ickjai Lee. (2009). Geographic forwarding and routing for ad-hoc wireless network: A survey. INC, IMS and IDC, 2009. NCM ’09. Fifth International Joint Conference on, 188-195.
[14] Li, L., Zhang, B., Shen, X., Zheng, J., & Yao, Z. (2011). A study on the weak barrier coverage problem in wireless sensor networks. Computer Networks, 55(3), 711-721.
[15] Liu, B., Dousse, O., Wang, J., & Saipulla, A. (2008). Strong barrier coverage of wireless sensor networks. Proceedings of the 9th ACM International Symposium on Mobile Ad Hoc Networking and Computing, 411-420.
[16] Saipulla, A., Westphal, C., Liu, B., & Wang, J. (2009). Barrier coverage of line-based deployed wireless sensor networks. INFOCOM 2009, IEEE, 127-135.
[17] Takagi, H., & Kleinrock, L. (1984). Optimal transmission ranges for randomly distributed packet radio terminals. Communications, IEEE Transactions on, 32(3), 246-257.
[18] Ting-Chao Hou, & Victor Li. (1986). Transmission range control in multihop packet radio networks. Communications, IEEE Transactions on, 34(1), 38-44.
[19] Zou, Y., & Chakrabarty, K. (2004). Sensor deployment and target localization in distributed sensor networks. ACM Transactions on Embedded Computing Systems (TECS), 3(1), 61-91.

指導教授

江振瑞

審核日期

2012-10-22

推文