基于移動無線傳感器網(wǎng)絡的k-階覆蓋算法

徐晉輝

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

基于移動無線傳感器網(wǎng)絡的k-階覆蓋算法

徐晉輝

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

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

無線傳感器網(wǎng)絡；移動；網(wǎng)絡覆蓋；分簇；VFA

1 引言

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

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

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

2 算法實現(xiàn)

2.1 定義問題

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

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

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

定義2：與網(wǎng)格四周相鄰的網(wǎng)格，稱為此網(wǎng)格的鄰居網(wǎng)格。

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

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

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

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

2.2 設計原理

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

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

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

2.3 網(wǎng)格化網(wǎng)絡

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

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

圖1 網(wǎng)格化網(wǎng)絡示意圖

2.4 決定移動序列

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

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

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

在傳感器網(wǎng)絡實現(xiàn)均勻覆蓋的同時，總的覆蓋面積也增加了不少，覆蓋面積S公式如下。

kCA算法偽代碼如下所示：

3 仿真

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

圖2 kCA與VFA算法的對比

4 總結

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

[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—)，女，安徽淮北人，實驗師，主要從事無線傳感器網(wǎng)絡研究。

(責任編輯 單麥琴)