無線感測網路具克服未知障礙物之機器人佈建演算法

Robot Deployment Algorithms for Wireless Sensor Networks with Unknown Obstacles

陳正昌(Cheng-Chang Chen)

指導教授 ： 張志勇

淡江大學/工學院/資訊工程學系博士班/博士(2016年)

https://doi.org/10.6846/TKU.2016.00710

摘要

無線感測網路(wireless sensor networks)中，良好的網路佈建方式與有效率的通訊協定，是無線感測網路中重要的議題，在近年來亦受到相當大的重視，本論文主要提出了高效的機器人感測器佈建演算法及高效的多頻道通訊協定，藉此提高無線感測網路的監測品質與傳輸效益。
首先，本論文針對感測器佈建議題進行探討，現存的佈建方法大都容易受到障礙物的影響，進而使機器人進入死巷或留下空洞。不同於現有的機器人佈建演算法，本論文所提出機器人佈建無線感測網路的演算法，僅以少量的記憶體成本讓機器人可以克服任何複雜的障礙物，並將適量的感應器佈建於監控區中以達到縮短佈建時間、節省感測器硬體成本及全區覆蓋等目的。此外，機器人僅需與已佈建的感測器進行少量通訊，使大多數已被佈建的感測器可進入省電狀態。
而感測器佈建後的通訊亦是相當重要的工作，近年來，發展多頻道媒體存取協定已受到極大的關注與討論，並被認為是開發頻寬利用率的有效方法。在發展多頻道通訊協定時所遭遇最大的挑戰便是主機會面問題(Rendezvous Problem)與多頻道隱藏節點問題(Multi-Channel Hidden Terminal Problem)。為解決會面問題，部分研究的作法是讓所有主機在特定的頻道中會面，以便進一步協調資料傳輸該使用的頻道。然而，此種作法將可能產生多頻道隱藏主機節點問題。另外，也有部分研究的作法，讓所有主機週期性地在特定頻道的ATIM Window聚集，以協調資料傳輸的頻道，但此種作法會造成其它頻道ATIM Window的頻寬利用率降低。為解決多頻道隱藏主機節點問題並改善多頻道傳輸時的頻寬利用率，本論文提出一多頻道MAC協定(SMC-MAC)，透過創新的階梯式頻道模型，將各頻道的控制區間錯開，並透過頻道對應函式，將各結點分散在不同的頻道中，藉此達成在不增加硬體成本下，有效解決多頻道的主機會面與多頻道隱藏主機節點問題，並提高頻寬利用率，進而提升網路傳輸效能。
我們透過大量的實驗與模擬，證明了本論文所提出的機器人佈建演算法具有高佈點率、低電力成本，且可以在複雜的監測區域中達到全區覆蓋。此外，本論文所提出的多頻道MAC協定可有效增加頻寬利用率，並提昇網路效能。

關鍵字

無線感測網路 ； 感測器佈建 ； 機器人 ； 感測覆蓋 ； 障礙物 ； 死路 ； 多頻道 ； 媒體存取控制協定 ； 會面問題 ； 隱藏節點問題

並列摘要

In wireless sensor networks (WSNs), the deployment and communication issues are very important and have received much attention in the last decade. This thesis mainly proposes efficient deployment and communication algorithms for improving the operating efficiencies of the wireless sensor networks.
First of all, the goal of developing a deployment algorithm is to deploy sensors in a given monitoring region in a way of low hardware cost and high coverage quality. In recent years, several mechanisms were developed for robot to deploy sensors efficiently. Their performances highly depend on the obstacles since their results are always inefficient when the Dead-End problem is encountered. Therefore, it has been the key challenge for developing a robot deployment mechanism to overcome the Dead-End problem and satisfy the full coverage requirement by using minimal number of sensors. This study proposes an Impasse-aware robot deployment algorithm, called IAD. The proposed IAD mainly consists of basic deployment rules and Dead-End handling rules. The basic deployment rules try to use minimal number of sensors such that the full coverage purpose can be achieved. Moreover, the proposed Dead-End handling rules can efficiently deal with the Dead-End problem. Extensive experiment studies show that our proposed IAD has better performance than existing robot deployment mechanisms in terms of coverage ratio, energy efficiency, deployment path length as well as required stack space.
In addition to investigating the deployment issue, this thesis also investigates the communication issues in WSNs. The Multi-channel media access control (MAC) protocols can increase wireless network capacities. The rendezvous problem is the most frequently encountered challenge in developing multi-channel MAC protocols. Some studies have assumed that each device is equipped with one additional antenna; however, this increases the hardware cost. Other studies have divided the timeline of each channel into several beacon intervals. All stations are awake simultaneously on a predefined channel to enable rendezvous opportunities; however, this leads to low bandwidth utilization. This thesis also presents an efficient staggered multichannel MAC protocol (SMC-MAC) for ad hoc networks. By using a single antenna, the proposed SMC-MAC applies a staggered channel model with a home channel concept for exploiting multi-channel bandwidth resources. Performance results reveal that the proposed SMC-MAC outperforms existing multi-channel MAC protocols in terms of network throughput, control packet collision ratio, packet delay time, packet discarding, packet loss ratio, control overhead, and robustness.
In summary, this thesis proposes robot deployment algorithm and MAC protocols for improving the efficiencies of the WSNs. Extensive experiment studies show that our proposed IAD has better performance than existing robot deployment mechanisms in terms of coverage ratio, energy efficiency, deployment path length as well as required stack space. In addition, the performance results reveal that the proposed SMC-MAC outperforms existing multi-channel MAC protocols in the network throughput, control packet collision ratio, packet delay time, packet discarding, packet loss ratio, control overhead, and robustness.

並列關鍵字

Wireless Sensor Network ； Sensor Deployment ； Robot ； Sensing Coverage ； Obstacle ； Dead-End ； Multi-Channel ； Medium Access Control ； Rendezvous Problem ； Hidden Terminal Problem

參考文獻

[1] R. V. Kulkarni, A.a Förster, and G. K. Venayagamoorthy, “Computational Intelligence in Wireless Sensor Networks: A Survey,” IEEE Communications Surveys & Tutorials, vol. 13, no. 1, pp. 68–96, Jan. 2011.

[2] E. Galceran and M. Carreras, “A survey on coverage path planning for robotics,” Robotics and Autonomous Systems, vol. 61, no. 12, pp. 1258–1276, Dec. 2013.

[3] L. Liu and H. Ma, "On Coverage of Wireless Sensor Networks for Rolling Terrains," IEEE Transactions on Parallel and Distributed Systems, vol. 23, no. 1, pp. 118–125, Jan. 2012.

[4] X. Li, D. K. Hunter, and S. Zuyev, "Coverage Properties of the Target Area in Wireless Sensor Networks," IEEE Transactions on Information Theory, vol. 58, no. 1, pp. 430–437, Jan. 2012.

[5] P. Zhang, I. Nevat, G. W. Peters, G. Xiao, and H.-P. Tan, “Event Detection in Wireless Sensor Networks in Random Spatial Sensors Deployments,” IEEE Transactions on Signal Processing, vol. 63, no. 22, pp. 6122–6135, Nov. 2015.