基于多目標遺傳算法的無線傳感器網絡重新部署方法

鄒長忠

(福州大學數學與計算機科學學院，福建福州 350116)

0 引言

無線傳感器網絡(WSNS)涉及眾多學科，擴展了人們的信息獲取能力，能夠獲取客觀物理信息，具有廣闊的應用前景．它主要由大量具有傳感能力和計算能力、數據傳輸能力的小型傳感節點構成．傳感器網絡部署問題是根據特定的要求，在給定的環境下，如何放置節點，達到預定的要求．其中很重要的一個指標就是覆蓋度．覆蓋可以有區域覆蓋、點集覆蓋、柵欄覆蓋．部署方面根據目標區域是否可以靠近，分為決定性部署和隨機性部署．但是在環境惡劣地方，如高原、雪山，或者要部署在敵區附近等這些人為不可能靠近的地方，只能采用隨機部署方法，即通過空投等方式．這樣必然造成節點分布不均，或者達不到任務要求．隨著可移動節點的引入利用，可以在隨機部署后，利用節點的移動來重新部署，達到預定的要求．文［1－5］利用虛擬合力算法，節點的移動依靠虛擬合力作用，節點沿合力方向虛擬移動，形成新的位置．文獻［6－10］提出基于計算幾何模型的節點部署方案．文［11］利用行列掃描法來均衡節點．文［12］將問題轉化為最小成本最大流問題，通過求解此問題，實現對網絡的優化部署．文［13］提出一種基于二部圖匹配的重新部署算法，將初始網絡描述成一個二部圖，圖的頂點集合由移動節點集合和需要覆蓋的網格集合組成．如果某個移動節點可覆蓋某個網格，則它們之間存在一條邊，衡量移動的花費可使用移動的距離、消耗的能量或跳躍的次數等．對構造的二部圖求其最小花費的最大匹配基，則該匹配基對應著一個最優的移動方案．文［14］提出結合虛擬合力和粒子群算法來優化網絡覆蓋．以上這些文獻考慮的部署均為單目標，即部署后使得區域覆蓋率最大化．文［15－21］提出多目標部署，文獻考慮的因素一個是覆蓋，另一個為網絡生命期，還有的考慮所用節點個數．文［22］利用遺傳算法，考慮區域覆蓋率和節點的移動量，但是設定的場合是節點的移動量是固定的，且求解問題也是將多目標利用加權方式轉為單目標，不能得到前沿解．

本文研究移動傳感器網絡，節點在隨機部署后，考慮不同節點移動量不同，確定最小化最大節點移動量和最大化網絡覆蓋率的雙目標前沿解．

1 網絡模型

網絡模型，目前傳感器網絡有三種感應模型:布爾、概率、信號強度．采用通用的布爾感應模型，即在檢測區域內的任何一個點，若其位于任意一個傳感器節點的感應半徑為圓形的感應區內，則稱該點被覆蓋．假設考慮的場景為一個平面長方形區域A，該區域長、寬分別為L，W．隨機空投n個網絡節點，用(x0i，y0i)表示節點i的初始位置，(0≤x0i≤L，0≤y0i≤W)．如圖1所示．

圖1 區域A示意Fig．1 The detection area A

定義1 網絡覆蓋率．區域內的某點p，如果存在一個節點si，使得d(si，p)≤Rs，其中d(si，p)為節點si與p的距離，Rs為節點的感應半徑，則稱點p被覆蓋．定義的網絡覆蓋率:

則計算:

定義2 節點移動量．節點i的當前位置為(xi，yi)，則節點i的當前移動量表示為:

我們的目標是整個區域的覆蓋率要大，而所有節點中的最大移動量要最小．這兩個目標是一對矛盾體，因為在初始隨機部署后，要增加覆蓋率，必然要移動節點，造成移動量增加．在極端情況下，所有節點在初始部署后不再移動，設節點是隨機均勻地投入區域A，則區域中任意一點被覆蓋的概率為:

2 多目標遺傳算法基礎理論

在給出具體的算法之前，先引用幾個關于多目標優化Pareto解的基本定義．

定義3 多目標優化函數．設D?Rn，x∈D為變量，fi(x):D→Rm為目標函數，gi(x)，hj(x):D→Rm為約束條件．含約束多目標極小化函數可以定義為:

定義4 Pareto占優．若向量u=(u1，u2，…，un)與向量v=(v1，v2，…，vn)存在這樣關系:?i∈{1，2，…，n}，有 ui≤vi，并且至少?i∈{1，2，…，n}，使得ui＜ vi，則稱u比v占優，計為u?v．

定義5 Pareto最優解．一個解x∈D是Pareto最優解，指不存在一個解x'∈D，使得f(x')?f(x)．

3 多目標遺傳算法的無線傳感器網絡部署

3．1 問題編碼

用實數表示染色體編碼，一個染色體即為一個可行解，表示n個傳感器節點的當前位置，并假設每個節點有固定的ID，ID從1到n依次排列，Pi(xj，yj)表示第i染色體個體即第j個節點當前位置為(xj，yj)，見表1．

表1 染色體i表示Tab．1 Chromosome i

3．2 交叉和變異算子選擇

交叉算法采用單點交叉操作，見表2、3．采用兩兩染色體隨機組合進行交叉，生成新的兩個染色體，采用虛擬合力算法，對染色體進行變異操作．

表2 單點交叉前Tab．2 Before single－point cross

表3 單點交叉后Tab．3 One－point crossover

變異操作:首先隨機選取某些染色體，隨機選取該染色體中某些個體，根據虛擬合力，確定這些個體節點的節點位置．

定義虛擬合力:

3．3 適應值函數

兩個目標函數，max f1(x)=C(A)，min f2(x)=max dsi

3．4 算法

步驟1:初始化，產生一個大小為2 000的隨機種群．

計算每個個體的覆蓋率指標和最大移動距離．

步驟2:基于NSGA－II，做非占優排序，產生非占優前沿(F1，F2，…，Fr)．同一個級別的Fi做擁擠距離排序．

步驟3:按非占優排序和擁擠距離排序后，選取k個個體．

步驟4:根據虛擬合力的交叉和變異操作從P產生后代P'．對P'中每個個體計算C(x)和dsi．

步驟5:合并P=P∪P';

判斷是否符合結束條件，若沒有則轉到第2步，否則結束．

4 仿真實驗

在CPU為Intel i7－3537U處理器，3．1 GHz內存為4 G PC機上，通過matlab2012b平臺實驗．選取仿真區域為300 m×300 m的平面區，傳感器感應半徑為15 m，通信半徑為20 m，隨機部署節點數為80個．在相同的節點初始位置下，設定虛擬合力距離閾值為7．5 m．遺傳算法變異概率若太大容易破壞種群的優良模式，若太小容易找到最優解，但是進化速度太慢．通過實驗測試發現，設定遺傳算法選取某染色體變異操作的概率為0．6，選取該染色體的某個體概率為0．2時，既能較好地保持上一代的占優解，又能防止算法過早地陷入局部最優解．分別設定種群大小為20，30和50．不同的種群大小下，得到的占優解分布圖(種群數20，30，50)見圖2，迭代800次．

從實驗結果發現，當節點移動距離比較小時，隨著移動量加大，網絡覆蓋率也明顯提高．而節點移動距離較大時，網絡覆蓋率提高有限，這是因為這時節點之間基本上不存在重疊現象，節點的移動對提高覆蓋率的作用很小．在與以上同樣的仿真環境下，設定種群大小為50，分別在迭代次數為500，800，1 000次時得到的占優解情況如圖3．本文算法與NSGA－II比較見圖4．

圖2 占優解(種群20)Fig．2 The dominant solution(population 20)

圖3 不同的迭代次數，得到的占優解分布圖(迭代次數:500，800，1 000)Fig．3 Different number of iterations，the resulting dominant solution(the number of iterations:500，800，1000)

圖4 本算法與NSGA－II比較Fig．4 This algorithm is compared with the NSGA －II algorithm

從圖3可以看出，迭代次數越多，那么離最優解越近，這是由于遺傳算法，采用保存當前占優解的結果．同樣到后面，由于節點之間的重疊率很低，所以迭代后期效果不明顯．

在同樣的迭代次數和初始條件下，從圖4可知，本算法得到的占優解比直接應用NSGA－II要好．主要是由于在節點的變異操作上采用基于虛擬合力算法，使得節點能往更多的空白方向移動，也即增大網絡覆蓋率方向移動，較快地接近實際最優解．

5 結語

在許多惡劣的情況下，傳感器網絡只能隨機部署．本研究通過節點的動態移動來增強覆蓋率，同時考慮節點的最大移動距離最小化．基于NSGA－II，利用選優和排序算法，引入虛擬合力對基因進行變異，達到網絡覆蓋率與節點移動距離之間的平衡，實驗證明，結果能得到較分散的前沿占優解．

［1］Howard A，Mataric M J，Sukhatme G S．Mobile sensor network deployment using potential fields:a distributed，scalable solution to the area coverage problem［C］//Proc of the 6th Int Symposium on Distributed Autonomous Robotics Systems．Fukuoka:［s．n．］，2002:299 －308．

［2］Hussein I，Stipanovic D M．Effective coverage control for mobile sensor networks with guaranteed collision avoidance［J］．IEEE Transactions on Control Systems Technology，2007，15(4):642－657．

［3］Zou Y，Krishnendu C．Sensor deployment andtarget localization based on virtual forces［C］//Proc of 22nd Annual Joint Conf of the IEEE Computer and Communications．San francisco:［s．n．］，2003:1 293 －1 303．

［4］Heo N，Varshney P．Energy－efficient deployment of intelligent mobile sensor networks［J］．IEEE Trans on Systems，Man and Cybernetics，2005，35:78 －92．

［5］Ma K，Zhang Y，Trappe W．Managing the mobility of a mobile sensor network using network dynamics［J］．IEEE Trans on Parallel and Distributed Systems，2008，19(1):106－120．

［6］Wang G，Cao G，La Porta T F．Movement－ assisted sensor deployment［J］．IEEE Trans on Mobile Computing，2006，6:640－652．

［7］Ma M，Yang Y．Adaptive triangular deployment algorithm for unattended mobile sensor networks［J］．IEEE Trans on Computers，2007，56(7):946 －958．

［8］Bartolini N，Calamoneri T F，La Porta T，et al．Autonomous deployment of heterogeneous mobile sensors［C］//Proc of IEEE ICNP，Princeton，2009:753－766．

［9］Tan G，Jarvis S A，Kermarrec A M．Connectivity－guaranteedand obstacle－adaptive deployment schemes for mobile sensor networks［J］．IEEE Trans on Mobile Computing，2009，8(6):836 － 848．

［10］Hummel K A，Sterbenz J P G．Self－ organizing systems［M］//Bartolini N，Calamoneri T，Fusco E，et al．Autonomous deployment of self－ organizing mobile sensors for a complete coverage．Vienna:Springer Berlin Heidelberg，2008:194 －205．

［11］Wu J，Yang SH．Smart:a scan－based movement－assisted deployment method in wireless sensor networks［C］//IEEE Conf on Computer Communications．Miami，2005:2 313 －2 324．

［12］Chellappan S，Bai X L，Ma B，et al．Mobility limitedflip － based sensor network deployment［J］．IEEE Trans onParallel and Distributed Systems，2007，18(2):199 －211．

［13］Cui C，Shen Z，Chang Y L，et al．Movement－assisted sensor network deployment algorithm for maximizing the networkcoverage［J］．Jof Xidian University，2009，36(2):222 －227;284．

［14］Wang Xue ，Wang Sheng，Ma Junji．An improved co－ evolutionary particle swarm optimization for wireless sensor networks with dynamic deployment［J］．Sensor Network，2012，20(3):12 －20．

［15］Ferentinos K P，Tsiligiridis T A．Adaptive design optimiza － tion of wireless sensor networks using genetic algorithms［J］．Comput Netw，2007，51(4):1 031－1 051．

［16］Molina G，Alba E，Talbi E G．Optimal sensor network lay－out using multi－objective metaheuristics［J］．JUniv Comput Sci，2008，14，(15):2 549－2 565．

［17］Kang C，Chen J．An evolutionary approach for multi－ objective 3d differentiated sensor network deployment［C］//Proc IEEE Int Conf CSE’09．Vancouver，2009:187 －193．

［18］Jourdan D B，deWeck OL．Layout optimization for a wireless sensor network using a multi－objective genetic algorithm［C］//IEEE Veh Technol Conf P．Los Angeles，2004:2 466 －2 470．

［19］Jia J，Chen J，Chang G，et al．Multi－ objective optimization for coverage control in wireless sensor network with adjustable sensing radius［J］．Comput Math Appl，2009，57(11/12):1 767 －1 775．

［20］Jia J，Chen J，Chang G，et al．Energy efficient cover－ age control in wireless sensor networks based on multi－ objective genetic algorithm［J］．Comput Math Appl，2009，57(11/12):1 756 －1 766．

［21］Konstantinidis A，Yang K，Zhang Q，et al．A multi－objective evolutionary algorithm for the deployment and power assignment problem in wireless sensor networks［J］．Comput Netw，2010，54(6):960 －976．

［22］匡林愛，蔡自興．基于遺傳算法的無線傳感器網絡重新部署方法［J］．控制與決策，2010，25(9):1 329－1 332．

［23］Deb K，Pratap A，Agarwal A，et al．A fast and elitist multi－objective genetic algorithm:NSGA［J］．IEEE Trans on Evolutionary Computation，2002，6(2):182－197．