| Abstract: | 在Wireless sensor networks (WSNs)環境中，監控區域的感測覆蓋面積會影響回傳到sink的監控資料精確度，如何將sensors佈置於特定欲監測區域內，並維持高效率的監測效能是個重要的議題。在網路佈建議題方面，sensors必須以低成本、高覆蓋的方式佈建在特定的監控區域裡。傳統最簡單的方式是隨機將sensors佈建在監控區域中，然而以隨機佈建會造成sensor佈建不均的問題。有鑑於此，本論文首先研發了有效率的克障機器人佈點（ORRD），藉由所提出之感測點佈建策略、蛇行狀移動機制及障礙物與邊界處理規則，使機器人能夠快速且花費最少的sensors數量佈點於監測區域，並有效地避開障礙物。接著，本論文另外提出了一機器人佈點演算法(OFPD)，同時考量避障礙物以及機器人移動時所產生的偏差問題，進行自我位置調整。透過機器人以螺旋形的移動機制以及遭遇障礙物時的規則處理，進行佈點的動作，進而減少機器人移動時所消耗的電量並達到完整覆蓋整個監控區域之目的。上述所提出的兩種機器人佈點演算法，雖然可以適用於絕大部分的網路環境，然而，當障礙物的形狀極度不規則時，
仍然有可能產生空洞及死路的問題，導致整個監控環境無法被完全覆蓋。此外，ORRD及OFPD皆未對機器人行走的路徑進行最佳化的動作，導致機器人在進行佈點的同時，可能會產生多繞路的問題。因此，本論文最終提出了一有效率的機器人佈點演算法(DFD)，以少量的記憶成本讓機器人幾乎可以克服任何複雜的障礙物並最佳化佈點路徑，將適量的感應器佈建於監控區中，同時達到縮短佈建時間、節省硬題成本及全區覆蓋等目的。實驗顯示，本論文所提出的演算法具有高佈點率、低電力成本，且可以在複雜的監測區域中達到全區覆蓋，並比現存的其他機器人佈點演算法有較佳的效能。
In wireless sensor networks(WSNs), coverage of the monitoring area represents the quality of service (QoS) related to the surveillance. Node deployment is one of the most important issues in providing the WSN with full coverage. Sensor nodes should be efficiently deployed in a predetermined region in a low cost and high coverage quality manner. Random deployment is the simplest way for deploying sensor nodes but may cause the unbalanced deployment and therefore increase the hardware cost and create coverage holes. This thesis initially presents an efficient obstacle-free robot deployment algorithm, called ORRD, which involves the designs of node placement policy, snake-like movement policy, obstacle handling rules, and boundary rules. By applying the proposed ORRD, the robot rapidly deploys near-minimal number of sensor nodes to achieve full sensing coverage even though unpredicted obstacles exit. Afterward, this thesis proposes an obstacle-free and power efficient-robot deployment algorithm, called OFPD which applies a spiral movement rule to overcome unpredicted obstacles, correct bias movement, and employ full-coverage deployment. By applying the OFPD, the number of deployed sensors can be significantly reduced and the purposes of full coverage and energy saving are likely achieved. In addition, the OFPD also takes into consideration the bias movement problem which is generally occurred in most commercial robots. Though the proposed ORRD and OFPD algorithms can deal with most irregular obstacles, however, the coverage hole, dead-end and long route length problem might be occurred in some other cases due to the obstacle shapes. Eventually, this thesis further proposes a dead-end free deployment algorithm, called DFD, which consists of Movement, Deployment and Dead-End handling rules. The Movement and Deployment rules ask robot to efficiently deploy a minimal number of sensors for achieving full coverage while the Dead-End handling rule overcomes the Dead-End problem and likely achieves full sensing coverage. Performance evaluations depict that the proposed obstacle-free deployment algorithms overcome the unpredicted obstacles and outperform the existing related work. |
