王騏，王青萍

　?。ê钡诙煼秾W(xué)院 物理與機(jī)電工程學(xué)院，湖北 武漢 430205）

       摘要：在資源受限、多跳的無線傳感器網(wǎng)絡(luò)中，節(jié)點(diǎn)分布或網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)不合理，將會產(chǎn)生感知陰影和覆蓋盲區(qū)，嚴(yán)重影響數(shù)據(jù)感知和網(wǎng)絡(luò)能效。為此提出一種基于節(jié)點(diǎn)移動的總適應(yīng)度的遺傳算法，通過節(jié)點(diǎn)的移動對節(jié)點(diǎn)進(jìn)行分簇和重定位，實現(xiàn)網(wǎng)絡(luò)節(jié)點(diǎn)覆蓋度的優(yōu)化和高能效的節(jié)點(diǎn)動態(tài)部署。仿真表明，算法對節(jié)點(diǎn)的重定位優(yōu)化了節(jié)點(diǎn)部署和路由配置，能量在各種不同功能性節(jié)點(diǎn)之間的分配更加合理，在適應(yīng)度參數(shù)保持平衡的情況下，減少了網(wǎng)絡(luò)內(nèi)節(jié)點(diǎn)“重分簇”的次數(shù)，最大限度地提高了網(wǎng)絡(luò)覆蓋度和生存期。

　　關(guān)鍵詞：動態(tài)部署；覆蓋度；能效；適應(yīng)度；遺傳算法；仿真

　　中圖分類號：TN918.91文獻(xiàn)標(biāo)識碼：ADOI： 10.19358/j.issn.1674-7720.2017.08.003

　　引用格式：王騏，王青萍.基于覆蓋度優(yōu)化的自適應(yīng)遺傳算法［J］.微型機(jī)與應(yīng)用，2017,36（8）：7-10，14.

　　0引言

　　*基金項目：湖北省高等學(xué)校優(yōu)秀中青年科技創(chuàng)新團(tuán)隊計劃項目(T201417)在無線傳感器網(wǎng)絡(luò)中，節(jié)點(diǎn)的分布以及網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的構(gòu)成，對于數(shù)據(jù)的感知和俘獲以及網(wǎng)絡(luò)的生存都具有十分重要的意義。在節(jié)點(diǎn)隨機(jī)部署的靜態(tài)傳感器網(wǎng)絡(luò)中，為了獲取良好的感知效果，在環(huán)境中往往會部署大于實際需要的冗余節(jié)點(diǎn)，因此網(wǎng)絡(luò)中有可能因為節(jié)點(diǎn)分布的不合理，造成感知陰影和覆蓋盲區(qū)［12］，使得有些被監(jiān)測事件無法進(jìn)行及時跟蹤。特別是當(dāng)某個特定區(qū)域需要多個傳感器節(jié)點(diǎn)協(xié)同感知數(shù)據(jù)時，如果這個區(qū)域節(jié)點(diǎn)分布稀疏，那么就無法完成更精準(zhǔn)的測量。在能效方面，由于傳感器節(jié)點(diǎn)負(fù)載的分布高度不均，當(dāng)向匯聚節(jié)點(diǎn)進(jìn)行數(shù)據(jù)傳遞時，那些遠(yuǎn)離匯聚節(jié)點(diǎn)的傳感器節(jié)點(diǎn)將會消耗大量能量，從而導(dǎo)致資源迅速枯竭。另外，由于單跳或多跳網(wǎng)絡(luò)的跳長固定不變，通信路徑無法優(yōu)化，不利于有效降低能耗。

　　相比于節(jié)點(diǎn)的靜態(tài)部署，基于節(jié)點(diǎn)移動性的動態(tài)部署能夠很好地解決上述問題。特別是在資源受限、多跳的移動傳感器網(wǎng)絡(luò)中，可通過節(jié)點(diǎn)的移動性構(gòu)建新的最短路徑，變多跳傳輸為少跳或單跳傳輸，從而縮短通信路徑，不僅可以均衡傳感器節(jié)點(diǎn)的負(fù)載分布，還可以最大限度減少通信開銷［3］。

　　本文基于對生物進(jìn)化機(jī)制的模仿，采用“進(jìn)化算法簇”中的遺傳算法（Genetic Algorithm，GA），實現(xiàn)節(jié)點(diǎn)分布的動態(tài)部署，進(jìn)一步優(yōu)化網(wǎng)絡(luò)節(jié)點(diǎn)的覆蓋度，最大限度提高電池和傳感器節(jié)點(diǎn)的使用壽命。

1遺傳算法適應(yīng)度函數(shù)的構(gòu)建

　　在網(wǎng)絡(luò)模型中按照功能將傳感器節(jié)點(diǎn)進(jìn)行了分類：（1）非活動節(jié)點(diǎn)（斷電狀態(tài)）；（2）簇頭（CH）；（3）簇間路由器（ICR）；（4）傳感器節(jié)點(diǎn)（NS）。遺傳算法的適應(yīng)度函數(shù)是用來判斷群體中個體的優(yōu)劣程度的指標(biāo)，它根據(jù)所求問題的目標(biāo)函數(shù)來進(jìn)行評估。在具體應(yīng)用中，適應(yīng)度函數(shù)的設(shè)計直接影響到遺傳算法的性能，因此要結(jié)合求解問題本身的要求來定。本節(jié)將介紹移動性的遺傳算法適應(yīng)度函數(shù)的構(gòu)建及其重要參數(shù)。

　　1.1覆蓋均勻性適應(yīng)度

　　覆蓋均勻性適應(yīng)度（Coverage Uniformity Fitness，CUF）表示覆蓋度的變化情況及其對環(huán)境的適應(yīng)能力。節(jié)點(diǎn)的移動可提高網(wǎng)絡(luò)覆蓋度，從而減小“覆蓋盲區(qū)”或增大監(jiān)測面積，這可通過重新調(diào)整簇內(nèi)成員節(jié)點(diǎn)之間的通信距離來實現(xiàn)。當(dāng)節(jié)點(diǎn)之間處于最佳距離時，相鄰節(jié)點(diǎn)間的最大距離以及所需的傳輸功率將趨于最小化，這有助于最大限度提高“節(jié)點(diǎn)通信適應(yīng)度NCF［4］”。CUF表示為：

　　其中M表示簇的數(shù)量，dj_min和dj_mean分別表示簇j內(nèi)節(jié)點(diǎn)間的最小通信距離和平均通信距離，ej_min 和ej_mean分別表示簇j內(nèi)節(jié)點(diǎn)與簇頭間的最小通信距離和平均通信距離。

　　1.2簇節(jié)點(diǎn)遷移適應(yīng)度

　　系統(tǒng)獎勵傳感器節(jié)點(diǎn)在具有較低“簇頭適應(yīng)度CHF［4］”的簇頭之間進(jìn)行遷移，以此來改進(jìn)傳感器節(jié)點(diǎn)和簇頭分布的均勻性，這種均勻性的改進(jìn)用簇節(jié)點(diǎn)遷移適應(yīng)度（ClusterNode Migration Fitness，CNMF）表示。簇節(jié)點(diǎn)遷移適應(yīng)度CNMF可表示為：

　　其中n表示第n個遷移對（源簇目標(biāo)簇），N表示遷移對的總數(shù)量，χns表示源簇內(nèi)冗余的傳感器節(jié)點(diǎn)數(shù)量，χnt表示目標(biāo)簇內(nèi)廢棄的傳感器節(jié)點(diǎn)數(shù)量，ρns和ρnt分別表示源簇和目標(biāo)簇內(nèi)簇頭下的節(jié)點(diǎn)數(shù)量，ρ表示每個簇的平均節(jié)點(diǎn)數(shù)，表示為：

　　從以上適應(yīng)度公式可看出，如果傳感器節(jié)點(diǎn)位于較低CHF的簇內(nèi)，且從源簇到目標(biāo)簇具有較高的擴(kuò)散梯度，那么這種情況有利于節(jié)點(diǎn)的遷移。

　　1.3簇頭遷移適應(yīng)度

　　簇頭遷移適應(yīng)度（ClusterHead Migration Fitness，CHMF）獎勵簇頭（CH）和具有較低“路由器負(fù)載適應(yīng)度RLF［4］”的簇間路由器（ICR）的移動。CH和ICR的移動可獲得較高的RLF，這是因為：

　?。?）ICR或CH的移動可改變ICR的成員身份，從而優(yōu)化CH/ICR的數(shù)量［4］。

　?。?）通過移動，ICR可與其他的功能性節(jié)點(diǎn)（簇頭和傳感器節(jié)點(diǎn)）交換角色。比如通過交換，可以使具有較高電池容量的節(jié)點(diǎn)作為路由器使用，這有利于維護(hù)現(xiàn)有的拓?fù)浣Y(jié)構(gòu)。

　　簇頭遷移適應(yīng)度（CHMF）可表示為：

　　CHMF=1N∑Nn11+ηn((1-RLFn)+ηn(1-BFns+BFnt))（6）

　　這里N表示移動的節(jié)點(diǎn)總數(shù)，RLFn表示第n個節(jié)點(diǎn)的“路由器負(fù)載適應(yīng)度［4］”，BFnt表示非ICR節(jié)點(diǎn)的“電池適應(yīng)度［4］”，它與第n個ICR節(jié)點(diǎn)（電池適應(yīng)度為BFns）進(jìn)行交換形成交換對。ηn是布爾值，表示第n個ICR的交換對是否存在。顯然，根據(jù)式（6）可知，具有較低的電池容量和路由器負(fù)載適應(yīng)度的ICRs和CHs是易于進(jìn)行移動的。

　　1.4節(jié)點(diǎn)移動適應(yīng)度

　　節(jié)點(diǎn)移動的平均距離與它的移動軌跡有關(guān)。由于節(jié)點(diǎn)的移動會消耗電池的能量，因此在有限的能量范圍內(nèi)，節(jié)點(diǎn)移動距離的期望值可看成是節(jié)點(diǎn)移動所需能量的估計值。所以，要實現(xiàn)優(yōu)化覆蓋度和提高網(wǎng)絡(luò)能效的總體目標(biāo)，需要保持節(jié)點(diǎn)移動特性的穩(wěn)定性，即節(jié)點(diǎn)移動的頻率和幅度。

　　節(jié)點(diǎn)移動適應(yīng)度（Node Motion Fitnes, NMF）可表示為：

　　NMF=(1－Fi(Q,distance)+(1－φi(n)))/2(7)

　　其中φi(n)表示對第i個傳感器節(jié)點(diǎn)進(jìn)行懲罰的一種度量，原因是它移動時位置不穩(wěn)定，到達(dá)同一個位置的次數(shù)達(dá)到n次(0≤φi(n)≤1）。Fi(·)表示第i個傳感器節(jié)點(diǎn)的懲罰函數(shù)，且0≤Fi(Q,NodeType)≤1，其中Q是電池的狀態(tài)，表示成一種量化步長，distance表示節(jié)點(diǎn)移動的預(yù)估距離，它是采用基于能量的定位方法，根據(jù)節(jié)點(diǎn)在不同位置的多個能量讀數(shù)間接估計出來的。

　　假定yi(t)表示第i個傳感器節(jié)點(diǎn)在時間間隔t內(nèi)的信號能量，則：

　　其中Gi表示第i個傳感器節(jié)點(diǎn)的增益因子，α(≈2）表示能量衰減因子，εi(t)表示參數(shù)建模誤差的累積效應(yīng)，S(t)表示目標(biāo)節(jié)點(diǎn)在時刻t釋放的能量，r(t)是D×1的向量，表示目標(biāo)節(jié)點(diǎn)在時刻t的坐標(biāo)，ri也是D×1的向量，表示第i個靜態(tài)傳感器節(jié)點(diǎn)的笛卡爾（直角）坐標(biāo)。

　　1.5傳感器節(jié)點(diǎn)數(shù)據(jù)適應(yīng)度

　　傳感器節(jié)點(diǎn)數(shù)據(jù)適應(yīng)度（Sensor Data Fitness，SDF）衡量的是傳感數(shù)據(jù)的效率，并據(jù)此重新定位傳感器節(jié)點(diǎn)，使其數(shù)據(jù)傳輸能通過融合、消除或壓縮等方式被統(tǒng)一優(yōu)化。在給定信噪比（SNR）下，通過提高傳感質(zhì)量還可使數(shù)據(jù)傳輸進(jìn)一步優(yōu)化［5］。在資源（通信、電池等）受限情況下的最佳傳感質(zhì)量可表示為θ(B,F)，其中B表示與傳感操作相關(guān)的QoS條件，F(xiàn)表示定時策略。實施QoS屬性是為了充分利用可變數(shù)據(jù)的壓縮和融合規(guī)則，而實施定時策略是為了根據(jù)傳感器節(jié)點(diǎn)的不同情況（比如說密度等）來改變比特率［6］。一般來說，降低簇的平均能耗有利于傳感器的移動。SDF表示為：

　　其中λ1+λ2=1，λ1和λ2可根據(jù)傳感器節(jié)點(diǎn)的運(yùn)行情況進(jìn)行自適應(yīng)調(diào)整。F={F1,F2,…,FN}和B={B1,B2,…,BN}分別表示簇n內(nèi)每個移動傳感器節(jié)點(diǎn)的平均移動頻率和傳輸比特率，φ(X,n)是關(guān)于隨機(jī)傳感器節(jié)點(diǎn)X的增益改進(jìn)，Xnμ和Xnσ分別表示簇n內(nèi)連續(xù)采樣樣本(s)的均值和方差。

　　1.6節(jié)點(diǎn)移動的總適應(yīng)度

　　根據(jù)以上所述，節(jié)點(diǎn)移動的總適應(yīng)度（Total Node Motion Fitness, TNMF）可表示為：

　　TNMF=α1CUF+α2CNMF+α3NMF+α4CHMF+α5SDF（11）

　　其中α1+α2+α3+α4+α5=1，單個αi的權(quán)值可根據(jù)外部啟發(fā)式算法［7］進(jìn)行自適應(yīng)調(diào)整。算法根據(jù)節(jié)點(diǎn)的運(yùn)行情況在一定時間內(nèi)進(jìn)行多階段決策過程的優(yōu)化處理，以最大限度取得單個αi的最優(yōu)組合值為目標(biāo)。

2節(jié)點(diǎn)部署遺傳算法

　　根據(jù)式（11），采用GA遺傳算子，可設(shè)計出節(jié)點(diǎn)的最優(yōu)動態(tài)部署算法。本節(jié)將介紹節(jié)點(diǎn)重定位的染色體表示，以及算法的主要流程。

　　2.1染色體的表示

　　GA的染色體是解決目前問題的關(guān)鍵模塊，形式上與遺傳算子和適應(yīng)度函數(shù)相適應(yīng)［8］。染色體串由每個傳感器節(jié)點(diǎn)的移動矢量形成，該矢量由7位二進(jìn)制數(shù)表示，稱為“基因”［9］，如圖1所示。

　　圖1基于遺傳算法的節(jié)點(diǎn)重定位及其染色體表示

　　將染色體串的層次結(jié)構(gòu)定義成：

　　((θ^xθxS^xS)1(θ^xθxS^xS)2(θ^xθxS^xS)3……)1……

　　((θ^xθxS^xS)1(θ^xθxS^xS)2(θ^xθxS^xS)3……)n

　　其中(θ^xθxS^xS)i表示節(jié)點(diǎn)的移動矢量，并具有以下特性：

　　(1)(θ^θ)表示0°(00)，90°(01)，180°(10)，270°(11)等角度的移動。

　　(2)(S^S)表示傳感器節(jié)點(diǎn)沿著給定方向移動的有限步數(shù)。

　　(3)只有當(dāng)其中一個x的值為1時，傳感器節(jié)點(diǎn)才會移動。

　　在圖1中，根據(jù)節(jié)點(diǎn)坐標(biāo)的變化，節(jié)點(diǎn)1、2的位置改變了3次，節(jié)點(diǎn)3、4改變了2次，而節(jié)點(diǎn)5、6、9只改變1次，其他節(jié)點(diǎn)沒有改變。因此，每個節(jié)點(diǎn)重定位后的染色體表示為：

　　2.2算法的流程

　　算法的流程如圖2所示。

　　產(chǎn)生初始種群時，初始染色體串一部分由隨機(jī)數(shù)發(fā)生器（RNG）產(chǎn)生，另一部分則由以前的種群樣本產(chǎn)生。每個染色體串根據(jù)TNMF函數(shù)（節(jié)點(diǎn)部署函數(shù)）對適應(yīng)度進(jìn)行評估，參見式（11）。繁殖使得具有較高適應(yīng)度的染色體串能夠以較大概率產(chǎn)生下一代染色體子串。因此，根據(jù)TNMF定義的適應(yīng)度公式，具有最高TNMF值的染色體將更有機(jī)會繁殖下一代染色體子串。繁殖期間，算法采用“標(biāo)準(zhǔn)加權(quán)輪盤”的方式，選擇n個染色體串投入到“配對庫”中，以“交叉概率”產(chǎn)生N個染色體。染色體繁殖期間，多個交叉點(diǎn)的位置由隨機(jī)數(shù)發(fā)生器（RNG）計算產(chǎn)生。染色體變異時，將生成的N個染色體放入突變庫，突變算子根據(jù)自適應(yīng)突變概率（與平均適應(yīng)度成反比）使其產(chǎn)生突變，采用類似拋硬幣的方式來決定是否要將比特位進(jìn)行逆變處理（即0→1，1→0）。設(shè)突變概率的最大值為pm，則：

　　pg=pm(1－(N*TNMFavg)/TNMFtotal)（12）

　　在選擇階段，根據(jù)適應(yīng)度值，從N+n個（n個雙親，N個孩子）染色體中選取n個染色體延續(xù)到下一代［10］。算法運(yùn)行時，比較每一次迭代得到的最優(yōu)適應(yīng)度，如果最大適應(yīng)度值和平均適應(yīng)度值變化不大、趨于穩(wěn)定，那么此適應(yīng)度值即為近似全局最優(yōu)解，算法終止，否則循環(huán)進(jìn)行。

3算法仿真與結(jié)果分析

　　仿真的實驗場景由100個節(jié)點(diǎn)組成，這些節(jié)點(diǎn)隨機(jī)分布在30×30的區(qū)間內(nèi)，每個節(jié)點(diǎn)具有唯一的UUID，隨機(jī)分配量化值介于0～15之間的電池容量，坐標(biāo)介于(0,0)～(30,30)之間。為簡化起見，每個節(jié)點(diǎn)覆蓋的范圍為3×3，并假定節(jié)點(diǎn)之間的通信為視距傳播（即無線信號的直線傳播）［11］。一旦所有的節(jié)點(diǎn)都處于監(jiān)聽模式，那么GA運(yùn)行時的交叉率為60%，初始變異率為6%。式（11）中節(jié)點(diǎn)移動的TNMF的單個αi組合值由外部啟發(fā)式算法運(yùn)行得到，α1～α5分別為：0.113 4、0.356 3、0.229 4、0.107 5、0.193 4。

　　實驗?zāi)M匯聚節(jié)點(diǎn)的運(yùn)行，NS2軟件模擬網(wǎng)絡(luò)的流量。盡管每個GA適應(yīng)度函數(shù)彼此存在競爭，但它們收斂于系統(tǒng)的平衡點(diǎn)，從而最大限度提高了網(wǎng)絡(luò)生存期，獲得了網(wǎng)絡(luò)的最佳覆蓋度。節(jié)點(diǎn)靜態(tài)和動態(tài)部署時，迭代次數(shù)與覆蓋度的函數(shù)關(guān)系如圖3所示。

　　從圖3可以看出，在節(jié)點(diǎn)具有移動性的動態(tài)部署中，覆蓋度增加了大約30%。但由于節(jié)點(diǎn)具有移動性，覆蓋度的增加也可能會導(dǎo)致通信開銷的增加，原因是：（1)對節(jié)點(diǎn)的移動指令進(jìn)行加密和認(rèn)證；（2)節(jié)點(diǎn)的移動可能會導(dǎo)致臨時數(shù)據(jù)包的丟失以及數(shù)據(jù)的損壞，從而引起通信路由上的安全認(rèn)證屬性進(jìn)一步增強(qiáng)。盡管節(jié)點(diǎn)重新部署會降低通信成本，但是節(jié)點(diǎn)的移動會增加電池成本，因此可能會降低系統(tǒng)的總體效益。

　　迭代次數(shù)與節(jié)點(diǎn)損失之間的關(guān)系如圖4所示。從此圖可以看出，動態(tài)部署明顯優(yōu)于靜態(tài)部署，損失的節(jié)點(diǎn)數(shù)減少15%～20%。在靜態(tài)部署情況下，節(jié)點(diǎn)的損失呈指數(shù)級，而在動態(tài)部署的情況下，由于總能量的分配更加優(yōu)化，節(jié)點(diǎn)在簇內(nèi)是逐漸消亡的。靜態(tài)部署方式下，節(jié)點(diǎn)的消亡會給覆蓋度帶來損失，由此會延長數(shù)據(jù)傳輸?shù)穆窂剑黾訑?shù)據(jù)傳輸?shù)哪芎摹?/p>

4結(jié)論

　　本文基于多目標(biāo)的遺傳算法，提出了一種移動傳感器節(jié)點(diǎn)的動態(tài)且高能效的部署方式。這種方式利用節(jié)點(diǎn)的移動性，以最佳方式對傳感器節(jié)點(diǎn)進(jìn)行重新定位，從而進(jìn)一步優(yōu)化節(jié)點(diǎn)的分配、路由配置，進(jìn)而最大限度提高網(wǎng)絡(luò)覆蓋度和生存期。在實驗中可以觀測到，由于節(jié)點(diǎn)的重定位提高了電池利用率（適應(yīng)度），因此能量在各種不同功能性節(jié)點(diǎn)之間的分配更加合理。在適應(yīng)度參數(shù)保持平衡的情況下，節(jié)點(diǎn)位置的改變會導(dǎo)致節(jié)點(diǎn)功能的改變，這也會減少網(wǎng)絡(luò)內(nèi)節(jié)點(diǎn)“重分簇”的次數(shù)。

參考文獻(xiàn)

　?。?］ 付華,韓爽.基于新量子遺傳算法的無線傳感器網(wǎng)絡(luò)感知節(jié)點(diǎn)的分布優(yōu)化［J］. 傳感技術(shù)學(xué)報,2008,21(7): 1259-1263.

　?。?］ 陳喻,王飛宇,楊任爾,等.利用sink的移動性提高無線傳感器網(wǎng)絡(luò)壽命［J］.機(jī)電工程, 2013,30(5):636-640.

　?。?］ 黃月,項妹,肖磊,等. 無線傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)部署問題研究［J］. 控制工程,2012,19(4):648-649.

　?。?］ KHANNA R, Liu Huaping， CHEN H H. Selforganization of sensor networks using genetic algorithms［C］. IEEE International Conference on Communication, Istanbul, 2006：33773382.

　?。?］ 張石,鮑喜榮,陳劍,等. 無線傳感器網(wǎng)絡(luò)中移動節(jié)點(diǎn)的分布優(yōu)化問題［J］. 東北大學(xué)學(xué)報(自然科學(xué)版), 2007,28(4):489-492.

　　［6］ 唐明虎，張長宏，昝風(fēng)彪. 無線傳感器網(wǎng)絡(luò)APIT定位算法［J］. 微型機(jī)與應(yīng)用，2010,29(21):1-4.

　?。?］ 班冬松,溫俊,蔣杰,等. 移動無線傳感器網(wǎng)絡(luò)k柵欄覆蓋構(gòu)建算法［J］. 軟件學(xué)報, 2011,22(9): 2089-2103.

　?。?］ 何璇, 郝群, 宋勇. 一種移動無線視頻傳感器節(jié)點(diǎn)的覆蓋算法［J］. 傳感技術(shù)學(xué)報, 2009, 22(8):1163-1168.

　　［9］ 葉苗,王宇平，代才，等. 無線傳感器網(wǎng)絡(luò)中新的最小暴露路徑問題及其求解算法［J］. 通信學(xué)報，2016,37(1):49-60.