王繼營,胡 君

(1.黃淮學院，河南 駐馬店 463000;2.湖南大學，湖南 長沙 410004)

0 引 言

采用靜態(tài)信宿的無線傳感網(wǎng)絡(Wireless Sensor Networks, WSNs)[1]易遭受信宿黑洞問題。信宿附近的節(jié)點能量消耗速度高于其他節(jié)點。一旦它們的能量耗盡，就造成覆蓋空洞，形成網(wǎng)絡斷裂。原因在于：信宿附近的節(jié)點需要轉發(fā)更多數(shù)據(jù)包[2]。

可采用多個信宿策略均衡傳感節(jié)點的能耗[3]。最為理想的策略是：采用單個信宿，信宿依據(jù)預定的路徑在網(wǎng)絡內(nèi)進行移動，并沿著路徑收集數(shù)據(jù)。信宿的移動，能夠平衡節(jié)點的能量消耗。相比于靜態(tài)信宿，移動信宿(Mobile Sink, MS)具有明顯的優(yōu)勢[4]。

然而，采用移動信宿的WSNs也存在一個問題：信宿如何移動，如何實現(xiàn)收集數(shù)據(jù)最大化。目前，有兩個策略解決此問題。其一，MS直接遍歷每個傳感節(jié)點，直接從每個傳感節(jié)點接收數(shù)據(jù)[5]；其二，允許MS遍歷一些預定的位置，這些位置稱為駐留點(Rendezvous Points, RPs)[6]。相比于前者，采用駐留點算法更有效，消耗的能量更少。

但是，如何搜索最優(yōu)的駐留點數(shù)以及它們的位置，進而獲取最大的數(shù)據(jù)收集量是駐留點算法必須解決的問題。當然，搜索最優(yōu)駐留點數(shù)以及最優(yōu)位置是NP問題。

遺傳算法廣泛應用于求解NP問題的近似解。遺傳算法以隨機初始可行解開始，這些隨機初始可行解稱為群體(Population)。群體內(nèi)的每個個體稱為染色體(Chromosome)。一條染色體是一系列的值，而每個值稱為基因(gene)。遺傳算法通過交叉、變異操作，最終能獲取最優(yōu)的群體，進而得到NP問題的次優(yōu)解。

為此，提出基于遺傳算法的搜索RPs (Genetic algorithm-based find RPs algorithm, GAFR) 算法。RAFR算法充分利用遺傳算法在求解NP問題上的優(yōu)勢，利用遺傳算法求解MS的RPs，進而構建最優(yōu)的移動路徑。仿真結果表明，提出的GAFR算法有效地降低了移動路徑，減少了數(shù)據(jù)收集時間。

1 問題描述

假定所有傳感節(jié)點隨機分布于方形網(wǎng)絡區(qū)域。利用GAFR算法獲取駐留點數(shù)及位置。MS通過遍歷駐留點[7]，從傳感節(jié)點收集數(shù)據(jù)。駐留點的初始位置是隨機的。每個MS具有足夠容量和能量計算遍歷路徑。當然，遍歷路徑需包含每個駐留點。為了表述簡單，引用以下的變量：

(1)傳感節(jié)點集S={s1,s2,…,sn}，其中n表示為傳感節(jié)點總數(shù)；

(2)駐留點集RP={r1,r2,…,rm}，其中m表示駐留點總數(shù)；

(3)用τ表示MS移動的總路徑長度，其近似等于駐留點間的距離之和，如式(1)所示：

(1)

其中χi,i+1表示第i個駐留點與第i+1個駐留點距離。

(4)令L0=0.2n、LF=0.5n分別表示一條信息素的最小長度、最大長度；

(5)令Sri表示第i個駐留點所覆蓋的傳感節(jié)點集；

(6)令K表示最優(yōu)駐留點數(shù)，最初K=m；

提出GAFR算法的目的在于尋找最優(yōu)K值，并且最小化MS遍歷的路徑。具體而言：(1)構建最優(yōu)K值，使得傳感節(jié)點能密集在分布于離其最近的駐留點周圍；(2)MS遍歷路徑長度τ最小。

綜上所述，可形式化表述所需解決的問題：

Minimize(τ)

(2)

約束條件：

|Sr1|+|Sr2|+|Sr3|+…+|Srm|=n

(3)

式(3)確保了MS能覆蓋所有傳感節(jié)點，進而能夠有效地收集數(shù)據(jù)。

2 GAFR算法

提出的GAFR算法主要由染色體表述、初始群體的產(chǎn)生、適度函數(shù)的構建、選擇、交叉和變異階段構成。

2.1 染色體表述

圖1 染色體表述

2.2 初始群體

對于不同長度的染色體，均采用固定的初始群體尺寸。若采用初始群體數(shù)為N，則只要滿足群體數(shù)為N的染色體才是有效的。群體數(shù)反應了可行解數(shù)。圖2顯示了長度為10、12的兩條染色體，但它們的群體數(shù)均為5(N=5)。

圖2 初始群體

2.3 適度函數(shù)

遺傳算法采用適度函數(shù)估計每條染色體的性能，并依據(jù)適度函數(shù)判斷染色體的合法性和非合法性。MS的最佳移動路徑取決于駐留點數(shù)。令L表示駐留點數(shù)或信宿的長度。同時，MS的最佳移動路徑也受τ的長度影響。

為此，利用L和τ這兩個因子構建適度函數(shù)，進而優(yōu)化最佳路徑。駐留點數(shù)少，路徑短，但可能會導致部分傳感節(jié)點無法覆蓋。反之，若駐留點數(shù)多，路徑會越長。同時，采用權重因子平衡這兩個因子，如式(5)所示：

F=αL+βτ

(5)

其中α、β為權重因子，且α+β=1。

2.4 選擇階段

在選擇階段，選擇部分染色體去執(zhí)行交叉、變異操作，進而產(chǎn)生新的種子(offsprings)[9]。為了能夠產(chǎn)生最優(yōu)的種子，選擇具有最優(yōu)的適度值的染色體進行操作。目前，有賭輪選擇(Roulette-wheel Selection)、秩值選擇算法。GAFR算法引用賭輪選擇算法，完成染色體的選擇。作為常用的選擇算子，賭輪選擇算法并不要求對個體先按適值排序。個體被選中的幾率與它的適應值呈正比。

2.5 交叉

將已選擇的染色體進行交叉操作。目前，也存在多種方式完成交叉操作，如單點交叉(Single-point crossover)、多點交叉(Multi-point crossover)。本文采用單點交叉操作。

如圖3所示，第一條染色體的長度為8，它的交叉點為紅實線；第二條染色體的長度為12，它的交叉點也為紅實線。兩條染色體通過交叉，完成信息交換，構成兩條新的染色體，且生成的子染色體長度均為10。

治療前，兩組2型糖尿病合并胃潰瘍患者在血糖水平差異無統(tǒng)計學意義（P>0.05）；治療后，觀察組2型糖尿病合并胃潰瘍患者空腹血糖（5.52±1.32）mmol/L、餐后 2 h 血糖（7.30±1.44）mmol/L，對照組空腹血糖（5.69±1.67）mmol/L、餐后 2 h 血糖（7.32±1.64）mmol/L，兩組間相比，差異無統(tǒng)計學意義（P>0.05）。見表2。

圖3 染色體交叉示意圖

2.6 變異

完成了交叉操作后，便可對新產(chǎn)生的子染色體進行變異[10]。通過變異，提高子染色體質(zhì)量。假定基因發(fā)生變異的概率為50%。變異后，必須保證新的子染色體能夠有效。

圖4顯示了變異過程。圖4顯示長度為10的染色體，第5個基因位置上發(fā)生變異，由原來的31變化成64，形成新的子染色體。

圖4 變異后的操作

圖5 GAFR算法流程

GAFR算法的整個流程如圖5所示，先產(chǎn)生初始群體，然后進行選擇操作，同時計算適度值，并選擇優(yōu)質(zhì)的染色體。再利用這兩項信息產(chǎn)生新的群體。隨后，利用交叉、變異產(chǎn)生新的子染色體。直到滿足終止條件，就停止。

3 性能分析

3.1 仿真環(huán)境

為了更好地分析GAFR算法的性能，選擇Python3.5軟件建立仿真平臺。在面積為S的方形區(qū)域內(nèi)部署50～300個傳感節(jié)點，迭代次數(shù)為1000。具體的仿真參數(shù)如表1所示。

表1 仿真參數(shù)

同時，選擇TSP算法作為參照。采用與GAFR算法相同的仿真參數(shù)，并對比分析它們的性能，包括MS移動的路徑長度、數(shù)據(jù)收集時間。

3.2 數(shù)據(jù)分析

考慮兩個實驗：實驗一，方形區(qū)域面積為：100 m2，傳感節(jié)點數(shù)從50變化至300；實驗二，方形區(qū)域面積為200 m2，傳感節(jié)點數(shù)從50變化至300。

3.2.1實驗一

首先，分析傳感節(jié)點數(shù)對路徑長度的影響，如圖6所示。

圖6 路徑長度(實驗一)

從圖6可知，節(jié)點數(shù)的增加，增長MS移動路徑。原因在于：節(jié)點數(shù)越多，分布區(qū)域越廣泛，MS需要收集的數(shù)據(jù)區(qū)域越廣，其需移動的路徑也就越長。相比于TSP算法，提出的GAFR算法有效地縮短了移動路徑。這要歸結于：GAFR算法利用遺傳算法搜索最優(yōu)的駐留點數(shù)，減少了移動路徑。

接下來，分析數(shù)據(jù)收集時間隨節(jié)點數(shù)的變化情況，如圖7所示。

圖7 數(shù)據(jù)收集時間(實驗一)

圖7的圖形走趨與圖6圖形相似。節(jié)點數(shù)的增加也提高數(shù)據(jù)收集時間。節(jié)點數(shù)越多，MS移動的路徑越長，相應地，數(shù)據(jù)收集時間也相應地增加。相比于TSP算法，提出的GAFR算法通過減少移動路徑，降低了數(shù)據(jù)收集時間。

3.2.2實驗二

相比實驗二，本次實驗改變了網(wǎng)絡區(qū)域面積。類似地，圖8、圖9顯示了在200 m2仿真環(huán)境下的路徑長度和數(shù)據(jù)收集時間。

圖8 路徑長度(實驗二)

圖9 數(shù)據(jù)收集時間(實驗二)

對比圖6可知，實驗二環(huán)境下的路徑長度得到較大幅度的增加。這正如預期的，網(wǎng)絡區(qū)域面積越大，節(jié)點分布區(qū)域也越廣，MS移動的路徑肯定越長。例如，當節(jié)點數(shù)在300時，網(wǎng)絡區(qū)域面積為100 m2時，TSP和GAFR算法的路徑長度分別為約1350和450；但當區(qū)域面積增加至200 m2時，它們的路徑長度分別增加至2500和900。

類似地，圖9的數(shù)據(jù)收集時間相比圖7(實驗一)大幅度地提升。原因在于：路徑的增長，增加了數(shù)據(jù)收集時間。對比圖7不難發(fā)現(xiàn)，網(wǎng)絡區(qū)域面積的增加，提高了數(shù)據(jù)收集時間。相比于TSP算法，提出的GAFR算法能夠有效地控制數(shù)據(jù)收集時間。

4 總 結

通過信宿的移動，能最大化WSNs的數(shù)據(jù)收集量。而信宿的移動路徑是基于移動信宿的數(shù)據(jù)收集的基本問題。提出的GAFR算法依據(jù)路徑長度、RPs數(shù)構建適度函數(shù)，再利用函數(shù)選擇最優(yōu)染色體，通過交叉、變異尋找最優(yōu)的RPs位置。仿真結果表明，提出的GAFR算法減少了數(shù)據(jù)收集時間，并縮短了移動路徑。