王騏,，王青萍

　　（湖北第二師范學院 物理與機電工程學院,，湖北 武漢 430205）

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

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

　　中圖分類號：TN918.91文獻標識碼：ADOI： 10.19358/j.issn.1674-7720.2017.08.003

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

　　0引言

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

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

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

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

　　在網(wǎng)絡(luò)模型中按照功能將傳感器節(jié)點進行了分類：（1）非活動節(jié)點（斷電狀態(tài)）,；（2）簇頭（CH）,；（3）簇間路由器（ICR）；（4）傳感器節(jié)點（NS）,。遺傳算法的適應(yīng)度函數(shù)是用來判斷群體中個體的優(yōu)劣程度的指標,，它根據(jù)所求問題的目標函數(shù)來進行評估。在具體應(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é)點的移動可提高網(wǎng)絡(luò)覆蓋度,，從而減小“覆蓋盲區(qū)”或增大監(jiān)測面積,，這可通過重新調(diào)整簇內(nèi)成員節(jié)點之間的通信距離來實現(xiàn)。當節(jié)點之間處于最佳距離時,，相鄰節(jié)點間的最大距離以及所需的傳輸功率將趨于最小化,，這有助于最大限度提高“節(jié)點通信適應(yīng)度NCF［4］”。CUF表示為：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

　　根據(jù)以上所述,，節(jié)點移動的總適應(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］進行自適應(yīng)調(diào)整。算法根據(jù)節(jié)點的運行情況在一定時間內(nèi)進行多階段決策過程的優(yōu)化處理,，以最大限度取得單個αi的最優(yōu)組合值為目標。

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

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

　　2.1染色體的表示

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

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

　　將染色體串的層次結(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é)點的移動矢量,，并具有以下特性：

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

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

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

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

　　2.2算法的流程

　　算法的流程如圖2所示。

　　產(chǎn)生初始種群時,，初始染色體串一部分由隨機數(shù)發(fā)生器（RNG）產(chǎn)生,，另一部分則由以前的種群樣本產(chǎn)生。每個染色體串根據(jù)TNMF函數(shù)（節(jié)點部署函數(shù)）對適應(yīng)度進行評估,，參見式（11）,。繁殖使得具有較高適應(yīng)度的染色體串能夠以較大概率產(chǎn)生下一代染色體子串。因此,，根據(jù)TNMF定義的適應(yīng)度公式,，具有最高TNMF值的染色體將更有機會繁殖下一代染色體子串。繁殖期間,，算法采用“標準加權(quán)輪盤”的方式,，選擇n個染色體串投入到“配對庫”中，以“交叉概率”產(chǎn)生N個染色體,。染色體繁殖期間,，多個交叉點的位置由隨機數(shù)發(fā)生器（RNG）計算產(chǎn)生。染色體變異時，將生成的N個染色體放入突變庫,，突變算子根據(jù)自適應(yīng)突變概率（與平均適應(yīng)度成反比）使其產(chǎ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ōu)適應(yīng)度,，如果最大適應(yīng)度值和平均適應(yīng)度值變化不大、趨于穩(wěn)定,，那么此適應(yīng)度值即為近似全局最優(yōu)解,，算法終止，否則循環(huán)進行,。

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

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

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

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

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

4結(jié)論

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

參考文獻

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

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

　?。?］ 黃月,項妹,肖磊,等. 無線傳感器網(wǎng)絡(luò)的節(jié)點部署問題研究［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é)點的分布優(yōu)化問題［J］. 東北大學學報(自然科學版), 2007,28(4):489-492.

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

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

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

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