基于移動無線傳感器網絡的k-階覆蓋算法

徐晉輝

(淮北職業技術學院 基礎部，安徽 淮北 235000)

基于移動無線傳感器網絡的k-階覆蓋算法

徐晉輝

(淮北職業技術學院 基礎部，安徽 淮北 235000)

在移動無線傳感器網絡中，傳感器節點可能由于自身移動、能量損失、物理損壞、錯誤和故障等因素的影響，從而出現覆蓋漏洞的情況，繼而導致網絡覆蓋效率低下。本文就此設計了一個新的移動無線傳感器網絡覆蓋算法，基于分簇的方式，而且能夠實時監測網絡中出現的覆蓋漏洞，并迅速進行修復。仿真結果表明，對于移動無線傳感器網絡，該算法不僅能夠實現所期望的覆蓋均勻度，還能夠增加覆蓋面積，提高網絡覆蓋率，而且性能要優于VFA。

無線傳感器網絡；移動；網絡覆蓋；分簇；VFA

1 引言

無線傳感器網絡是伴隨無線通信和嵌入式計算技術、傳感器技術、微機電技術、分布式信息處理技術的進步而發展起來的一種新興的信息獲取技術，是目前國際上備受關注的、多學科高度交叉、知識高度集成的前沿熱點研究領域[1]。無線傳感器網絡中的每個節點都含有一個多功能傳感器，它們不僅體積小、價格便宜、低能耗、支持短距離通信，而且還具備信息采集、數據處理、數據傳輸、相互通信的功能。因此，無線傳感器網絡能夠通過各類集成化的微型傳感器協作地實時監測、感知和采集目標環境或監測對象的信息，然后通過自組多跳的無線傳播方式傳送給用戶終端，從而實現物理世界、計算世界以及人類社會三元世界的連通。

隨著無線傳感器網絡在技術與應用方面的驚人發展，其中的一點就是得到了移動領域方面的快速關注。可將傳感器網絡的移動性分成兩類：內部移動性和外部移動性[2]。內部移動性指的是：在傳感器網絡范圍內，傳感器自己能夠從一個位置移動到另一個位置。該分類的一個典型實例：將傳感器安置在一個移動平臺上(機器人)，它能夠自行決定來作出移動，從而完成一些特定的任務目標，比如：修復網絡覆蓋漏洞，從而達到更好的感應效果。另一方面，外部移動性指的是：特定的外部代理在傳感器網絡中的移動。該分類的一個典型實例：一種交通工具或者一個士兵，為了收集數據、補充傳感器能量、以及節點定位等目的，在傳感器網絡中的移動。

當網絡中的一些傳感器由于故障，能量損失等原因而失效時，就會產生網絡覆蓋漏洞，進一步影響網絡連通性。此時，就可以通過移動傳感器來修復，從而提高網絡覆蓋率，增加網絡覆蓋面積，實現均勻覆蓋，增強網絡連通性等目的。移動傳感器還能夠通過移動到事件發生的附近，得到更好的感應，從而加強事件的檢查質量和可靠性。相對于靜態傳感器節點，移動傳感器節點能夠實現更高程度的覆蓋和連接[3-5]。本文設計了一個新的移動傳感器網絡覆蓋算法，不僅能夠有效地提高網絡覆蓋率，而且還大大增加了網絡覆蓋面積，可以達到特定的覆蓋均勻度，充分利用傳感器節點的能量，從而延長網絡的使用壽命，提高網絡的綜合應用性能。

2 算法實現

2.1 定義問題

本文研究的對象是移動無線傳感器網絡，通過隨機部署的方式將傳感器節點散播在目標區域范圍之內，然后根據具體應用需求，把目標區域劃分成若干個小正方形，我們稱這樣的小正方形為網格。在對整個傳感器網絡網格化的基礎之上，實時監測網絡中存在的覆蓋漏洞，并迅速進行相應地修復。

假設：移動傳感器網絡所覆蓋的目標區域為一個長方形區域，用A來表示，區域的長為L，寬為R。初始部署時的傳感器數目為N，且其ID號為Si，用于唯一標識傳感器節點。為了定位好傳感器節點，我們用Loc_Si來表示它們的位置，其坐標為(xi，yi)。在本文中，每個傳感器都是同構的，而且都能夠通過GPS來獲取自身當前的位置信息。傳感器的感知半徑為Rs，連通半徑為Rc，生命周期為T，每次移動距離為 F。網格的邊長為 Rgrid，且其 ID 號為 Gri，j，網格內對應的傳感器數目為Numi，j。期望值為k，用來表示每個網格內希望所部署的傳感器數目。

定義1：傳感器節點的 ID 為 Si，i<=N，且i∈Z。

定義2：與網格四周相鄰的網格，稱為此網格的鄰居網格。

定義3：當傳感器節點從當前網格移向一個鄰居網格時，稱此次移動為一跳。

定義5：兩個傳感器節點的歐氏距離為

定義7：本文所提的基站指的就是匯聚節點(Sink節點)。

定義8：如果 Numi，j＝0，則 Gri，j為覆蓋漏洞。

2.2 設計原理

本文所提出的算法是運行在基站上，屬于集中式的覆蓋算法。針對目標區域A，傳感器網絡中的每個節點，能夠通過GPS來決定自身的位置，然后再將位置信息轉發給基站。因此，基站就能夠通過這樣的方式來收集每個網格內的傳感器信息，并將這些傳感器位置信息存儲在基站上。待信息收集完畢之后，基站就會針對整個傳感器網絡，并將其劃分成m×n個網格。同時，在基站上記錄每個網格的傳感器數目。

當網絡全部網格化之后，首先進行橫向掃描，實現橫向網格內傳感器數目的均勻化。接著進行縱向掃描，實現縱向網格內傳感器數目的均勻化。通過一次橫縱掃描就可以基本實現整個網絡的全局覆蓋均勻化，再結合網格內傳感器的有關信息來決定移動序列(哪個傳感器應該移動，移動到哪里)，輪循執行該算法，可以最終實現全局覆蓋均勻化。每執行一次該算法，得出移動序列之后，都是通過基站來將移動序列轉發給網絡中相應的傳感器，控制其移動。

在整個網絡運行的過程中，基站是能夠沿著網絡四周的邊緣進行移動，并收集傳感器節點的相關信息，以減少網絡成員節點的能量損耗，從而延長整個網絡的使用壽命。算法的運行策略，屬于集中式的，通過基站運算得出移動序列，再將指令發送給傳感器節點，控制傳感器的移動。基站還能夠對整個網絡進行實時監控，一旦發現網絡覆蓋漏洞，就會及時修復。

2.3 網格化網絡

當移動無線傳感器網絡初始部署之后，所有的傳感器節點就會通過使用自身配置的GPS設備來獲取當前的位置，并將其存儲在Loc_Si當中，繼而將該信息數據包和自身ID號Si一并轉發給基站。在基站收到這些信息之后，就會先將這些信息存儲起來，然后再將其ID號Si發送給相應的傳感器節點，以示確認收到此信息。經過一段時間之后，如果網絡中沒有位置信息數據包轉發了，基站就會廣播一次所收到的全部位置信息給相應的傳感器節點，當這些節點收到此時的信息數據包后，就會再回復一個自身的ID號Si信息數據包給基站，來確認自身存在于該傳感器網絡當中。在基站進行信息采集完成之后，就會根據該次收到的ID號Si信息數據包來建立一個數組Loc[N]，用于存儲整個網絡中傳感器節點的位置信息。而且，此數組是以傳感器節點的ID號Si來順序存儲對應的位置信息，如公式(1)所示。如果其間有的ID號沒有對應的位置信息，就會將其值置0，用來表示網絡中不存在該傳感器節點。

在位置信息采集并存儲完成之后，基站首先會找出最靠近網絡邊緣的東南西北方向上的四個傳感器節點位置，接著找出傳感器部署最密集的地方，再根據k的值和網格邊長Rgrid來共同決定目標監測區域A的范圍。此時，整個傳感器網絡的網格化已經建成。在基站上會根據傳感器的位置來確定它們所在的網格，并建立一個二維數組Grid[i][j]，用于存儲網格的 ID 號 Gri，j和網格內的傳感器數目 Numi，j，如圖1所示。長方形指的就是目標監測區域A，長為L，寬為R。在長方形內的正方形小方格表示的就是網格，其左上角藍色數字表示的就是網格ID號，如Gr1，1＝1。黑色圓圈表示網格內的傳感器，圓圈內的數字表示當前網格內的傳感器數目，如Num1，1＝6。第一個網格上邊的紅色線條表示網格的邊長Rgrid。

圖1 網格化網絡示意圖

2.4 決定移動序列

在網絡網格化之后，就便于計算出傳感器節點的移動序列。利用二維數組Grid[i][j]，可以先計算數組中每行的傳感器數目之和，再對每行求均值ki，求出的ki就表示所有橫向網格內傳感器數目的均值。

當求出每行的均值之后，接著就找出每行中傳感器數目最大的列，并以該列為中心，通過移動該列內的傳感器節點，來保持以該列為中心的兩邊傳感器數目相等。然后分別對該中心兩邊的傳感器進行遞歸操作，當該行內傳感器的數目都基本接近ki為止，即｜Numi，j-ki｜<=1。在所有橫向網格內的傳感器都均勻化之后，就進行縱向掃描。縱向掃描的方法和橫向掃描的方法基本一樣，只是先得求出每列的均值kj，求出的kj就表示所有縱向網格內傳感器數目的均值。最后算出的kj，其值就等于期望值k。

通過橫縱兩次掃描之后，整個傳感器網絡已經基本實現均勻化了。如果網絡中還有覆蓋漏洞或者覆蓋不均勻的情況存在的話，就可以再運行算法進一步調整網絡部署，以實現整個傳感器網絡最均勻化，也就是均勻度I取最小值的時候。

在傳感器網絡實現均勻覆蓋的同時，總的覆蓋面積也增加了不少，覆蓋面積S公式如下。

kCA算法偽代碼如下所示：

3 仿真

N表示網絡中傳感器的數目，仿真過程采用了N＝200和N＝100兩種方式。實驗主要是為了驗證傳感器網絡在初始部署和最終部署時的覆蓋面積和覆蓋均勻度，也就是利用公式(1)和(2)，在算法執行之后，都有明顯增加和提高，如圖2所示。實驗還仿真了VFA算法[6]，并與文中設計的算法進行了對比。由于本文算法在簇內結合應用了VFA算法，從而實現了局部優化部署，有效地避免了VFA算法中出現的傳感器來回往返移動的情況。因此，在總體上節省了不少能量，延長了網絡的使用壽命。

圖2 kCA與VFA算法的對比

4 總結

通過反復執行mWSNkCA算法，可以使得移動無線傳感器網絡增加覆蓋面積，并達到所期望的覆蓋均勻度，不僅能夠修復網絡中存在的覆蓋漏洞，還能夠增強網絡的連通性，確保數據的有效傳輸。在算法執行的前期，網絡中的傳感器部署能夠實現局部的均勻覆蓋，但最終能夠實現全局的均勻覆蓋。

[1]Akyildiz I.F.，Su W.,Sankarasubramaniam Y.Wireless Sensor Networks:a Survey[J].Computer Networks.2002，38(4)：393-422.

[2]Sriram Chellappan.On Deployment and Security in Mobile Wireless Sensor Networks:Algorithms Design,Vulnerability Assessment and Analysis[M].ISBN:363918257X.VDM Verlag,July 2009，(19)：11-23.

[3]T.Cormen，C.Leiserson，R.Rivest and C.Stein.Introduction to algorithms[M].in MIT Press，2001.

[4]A.v.Goldberg.An efficient implementation of a scaling minimum-cost flow algorithm[J].J.Algo rithms 1997.22.

[5]A.V.Goldberg and R.Tarjan. Solving minimum-cost flow problems by successive approximation[C]//in Proceedings of ACM Symposium on Theory of Computing (STOC)，(New York)，May 1987.

[6]Yi Zou and Krishnendu Chakrabarty.Sensor Deployment and Target Localization Based on Virtual Forces[C]//IEEE INFOCOM 2003.

Mobile Wireless Sensor Networks Based on K-covering Algorithm

Xu Jin-hui
(Huaibei Vocational&Technical Collgeg，Huaibei Anbui 235000)

In mobile wireless sensor network，considering that sensors node may be in the intersection of no-signal area due to the causes of its move，the energy loss，physical damage，errors，failures and so on，leading to less effect of the network-covering.This paper designed a new algorithm for mobile wireless sensor network coverage，clustering-based approach，can monitoring the network coverage holes in real-time and quickly repaired.Simulation results show that for mobile wireless sensor network，the algorithm can achieve the desired uniformity of coverage，increased coverage，improved network coverage，and its performance is better than VFA.

wireless sensor network；mobile；network coverage；cluster；VFA

TP39

A

1673-2014(2012)02-0064-04

2012—03—18

徐晉輝(1973—)，女，安徽淮北人，實驗師，主要從事無線傳感器網絡研究。

(責任編輯 單麥琴)