基于蒙特卡羅算法的點覆蓋問題解決方法

摘要：在WASN (wireless Ad hoc sensor network)中，點覆蓋是一個基本問題。在考慮傳感器節點移動的情況下，提出一個基于蒙特卡羅算法的目標點的集合覆蓋質量評估算法，該算法每次從目標點集合中任意選取若干點進行評估，若全部滿足覆蓋質量要求則返回，否則標定不滿足條件的目標點。反復調用該算法五次，可以使覆蓋質量評估算法的正確率達到99%，從而可以有效解決無線傳感器網絡中的點覆蓋問題。模擬證明該算法是可行的。

關鍵詞：點覆蓋； 蒙特卡羅算法； 監聽質量； 部署

中圖分類號：TP393文獻標志碼：A

文章編號：1001-3695(2007)12-0083-02

0引言

傳感器節點，又稱為無線傳送器，是一種具有感知、計算、存儲和通信功能的器件。傳感器節點組成大規模的網絡來完成一個感知任務。比如要檢測一片森林的平均溫度，那么需要在森林中均勻地布置大量的傳感器，每個傳感器將探測到的溫度發送給sink節點，再由它傳送到主機集中處理。

WASN的主要特征是節點的隨意部署（如飛機空投），所以預先無法知道節點的確定位置。這可以用于戰爭或者救災等，因為在這些情況下，無法在目標區域準確地放置傳感器節點。WASN的特征還包括有限資源、大規模的密集網絡、動態拓撲結構。通常情況下，為了完成給定的任務，用戶要比預算投入更多的節點，以彌補無法準確定位的缺點。

覆蓋問題是當今WASN研究中的一大熱點。根據監聽目標的種類，它分為區域覆蓋和目標點覆蓋。后者是用來監測一些目標點附近的狀況，如有無火災、污染程度等。在考慮傳感器節點可以移動的情況下，此時拓撲結構的動態變化導致目標點集合被傳感器網絡監聽的質量不穩定。本文用蒙特卡羅算法來評估該監聽質量，從而實施傳感器節點的進一步部署，為以后的分組工作做好準備。

1相關工作

一般地，覆蓋反映了一個區域或者目標點的集合被傳感器監聽的程度。關于覆蓋問題的相關工作主要集中在k－cover判斷和進一步的節點部署上。在區域覆蓋的研究方面，Dhillon等人^[1]將傳感器區域分成網格，引進了發現概率矩陣來決定在哪個網格中放置傳感器。文獻[2]中引進了maximal breach path（MBP）和maximal support path（MSP）來評估傳感器節點分布稀疏度的算法，即尋找最大缺口，然后再在其中加入一些傳感器節點使整個區域的傳感器密度均勻。類似地，文獻[3]介紹了一個傳感器網絡的暴露程度（exposure）的概念。Huang等人^[4]給出了一種在節點不可以移動下的判斷各個區域的傳感器監聽質量的算法。文獻[5]中指出，為了延長系統的生命期，將整個傳感器節點集分割成互不相交的子集，而且每個子集均能覆蓋整個區域，從而可以輪流工作，算法的目標就是讓子集數最大。作者給出了三種算法來完成以上的任務。

6結束語

在節點的隨意放置和動態拓撲結構下，本文使用了蒙特卡羅算法來評估目標點被傳感器網絡監聽的質量，進而實施新的部署，通過模擬驗證性能優良。將來的工作就是針對算法H中的部署問題進行研究。

參考文獻：

[1]DHILLON S S， CHAKRABARTY K. Sensor placement for effective coverage and surveillance in distri－buted sensor networks[C]//Proc of IEEE Wireless Communications and Networking Record.[S.l.]:IEEE Press， 2003:1609-1614.

[2]MEGUERDICHIAN S，KOUSHANFAR F， POTKONJAK M， et al. Coverage problems in wireless Ad hoc sensor networks[J].IEEE INFOCOM，2001，3:1380-1387.

[3]MEGUERDICHIAN S， KOUSHANFAR F， QU G， et al.Exposure in wireless Ad hoc sensor networks[C]//Proc of Annual International Conference on Mobile Computing and Networking. New York:ACM Press，2001:139-150.

[4]HUANGC F， TSENG Y C. The coverage problem in a wireless sensor network[J].Journal of Internet Technology， 2005，6（1）：1-8.

[5]ZOE A， ASHISH G， SERGE P. Set k－cover algorithms for energy efficient monitoring in wireless sensor networks[C]//Proc of the 3rd International Symposium on Information Processing in Sensor Networks. New York:ACM Press，2004:424-432.

[6]CARDEI M， DU D Z.Improving wireless sensor network lifetime through power aware organization[J].Wireless Networks， 2005，11(3):333-340.

[7]KAR K， BANERJEE S. Node placement for connected coverage in sensor networks[J]. Modeling and Optimization in Mobile，Ad hoc and Wireless Networks，2003，5:213-219.

[8]DOHERTY L， PISTER K S J，GHAOUI L E. Convex optimization methods for sensor node position estimation[C]//Proc of IEEE INFOCOM. Anchorage:[s.n.]，2001:213-220.

[9]SAVVIDES A， PARK H， SRIVASTAVA M. The bits and flops of the n－hop multilateration primitive for node localization problems[C]//Proc of WSNA. Atlanta:[s.n.]， 2002:112-121

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”