異質方向性行動感測器佈署問題之加強型協定設計

Enhanced Deployment Protocols for Heterogeneous Directional Mobile Sensors in a Bounded Monitoring Area

吳佩真(Pei-Jhen Wu)

指導教授 ： 林亭佑

國立交通大學/電機學院/電信工程系所/碩士(2012年)

https://doi.org/10.6842/NCTU.2012.00155

摘要

良好的感測器佈署方式能使網路獲得有效的監控能力。不同於以往的全向性感測器，方向性感測器的感測範圍不只與感測半徑(距離)有關，並且也與感測器 的方向和感測器的感測角度大小有關。基於材質與製作流程等之各種因素，不同 的感測距離和感測角度大小是有可能存在在方向性感測器上的。我們發現單純在 一個固定點上旋轉感測器的方向並不能有效的提高整體感測覆蓋率。因此在此篇 論文裡，我們針對可移動且可旋轉的異質方向性感測器作討論，利用我們所提出 的兩種加強型佈署演算法(EDA-I、EDA-II)讓感測器能夠在欲監控範圍中完成自 我佈署且提升整體感測覆蓋率。 在 EDA-I 中，我們將擁有不同的感測半徑及感測角度的方向性感測器對應到 虛擬全向性感測器並利用這些虛擬感測器計算出各個方向性感測器應該到達的 位置，而 EDA-II 則是藉由 Voronoi diagram 的運算來輔助感測器完成自我佈署的工作。在此篇論文中，我們提出了一個全新的概念:virtual boundary torques，藉由virtual boundary torques 我們除了可以更有效的提升感測覆蓋率外，也可以減少因感測器移動過多距離所產生的能量消耗。最後的模擬結果證實了我們的加強型佈署機制能夠在不需要耗費大量移動能量及計算時間的條件下提供令人滿意的監控能力。

關鍵字

方向性感測器佈署 ； 感測覆蓋率 ； 虛擬邊界力矩 ； 無線感測網路

並列摘要

Good deployment of sensors empowers the network with effective monitoring ability. Different from omnidirectional sensors, the coverage region of a directional sensor is determined by not only the sensing radius (distance), but also its sensing orientation and spread angle. Heterogeneous sensing distances and spread angles are likely to exist among directional sensors, to which we refer as heterogeneous directional sensors. In this paper, we target on a bounded monitoring area and deal with heterogeneous directional sensors equipped with locomotion and rotation facilities to enable the sensors self-deployment. Two deployment algorithms, EDA-I and EDA-II, are proposed to achieve high sensing coverage ratio in the monitored field. EDA-I leverages the concept of virtual forces (for sensors movements) and virtual boundary torques (for sensors rotations), whereas EDA-II combines Voronoi diagram directed movements and boundary torques guided rotations. Performance results demonstrate that our enhanced deployment mechanisms are capable of
providing desirable surveillance level, while consuming moderate moving and rotating energy under reasonable computation time.

並列關鍵字

Directional sensors deployment ； sensing coverage ； virtual boundary torques ； wireless sensor network

參考文獻

[1] J. Ai and A. A. Abouzeid. ”Coverage by Directional Sensors in Randomly Deployed Wireless Sensor Networks”. Journal of Combinatorial Optimization, 11(1):21–41, February 2006.

[2] F. Aurenhammer. ”Voronoi Diagrams - A Survey of a Fundamental Geometric Data Structure". ACM Computing Surveys, 23(3):345–405, September 1991.

[3] E. S. Biagioni and K. W. Bridges. ”The Application of Remote Sensor Technology to Assist the Recovery of Rare and Endangered Species ”. Int’l Journal of High Performance Computing Applications, 16(3):315–324, 2002.

[4] W. Cheng, S. Li, X. Liao, S. Changxiang, and H. Chen. ”Maximal Coverage Scheduling in Randomly Deployed Directional Sensor Networks”. In Proc. Int’l Conf. Parallel Processing Workshops (ICPPW), September 2007.

[5] S. Fortune. ”A Sweepline Algorithm for Voronoi Diagrams”. Algorithmica, 2:153–174,1987.