王騏，王青萍

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

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

　　關鍵詞：動態部署；覆蓋度；能效；適應度；遺傳算法；仿真

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

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

　　0引言

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

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

　　本文基于對生物進化機制的模仿，采用“進化算法簇”中的遺傳算法（Genetic Algorithm，GA），實現節點分布的動態部署，進一步優化網絡節點的覆蓋度，最大限度提高電池和傳感器節點的使用壽命。

1遺傳算法適應度函數的構建

　　在網絡模型中按照功能將傳感器節點進行了分類：（1）非活動節點（斷電狀態）；（2）簇頭（CH）；（3）簇間路由器（ICR）；（4）傳感器節點（NS）。遺傳算法的適應度函數是用來判斷群體中個體的優劣程度的指標，它根據所求問題的目標函數來進行評估。在具體應用中，適應度函數的設計直接影響到遺傳算法的性能，因此要結合求解問題本身的要求來定。本節將介紹移動性的遺傳算法適應度函數的構建及其重要參數。

　　1.1覆蓋均勻性適應度

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

　　其中M表示簇的數量，dj_min和dj_mean分別表示簇j內節點間的最小通信距離和平均通信距離，ej_min 和ej_mean分別表示簇j內節點與簇頭間的最小通信距離和平均通信距離。

　　1.2簇節點遷移適應度

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

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

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

　　1.3簇頭遷移適應度

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

　?。?）ICR或CH的移動可改變ICR的成員身份，從而優化CH/ICR的數量［4］。

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

　　簇頭遷移適應度（CHMF）可表示為：

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

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

　　1.4節點移動適應度

　　節點移動的平均距離與它的移動軌跡有關。由于節點的移動會消耗電池的能量，因此在有限的能量范圍內，節點移動距離的期望值可看成是節點移動所需能量的估計值。所以，要實現優化覆蓋度和提高網絡能效的總體目標，需要保持節點移動特性的穩定性，即節點移動的頻率和幅度。

　　節點移動適應度（Node Motion Fitnes, NMF）可表示為：

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

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

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

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

　　1.5傳感器節點數據適應度

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

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

　　1.6節點移動的總適應度

　　根據以上所述，節點移動的總適應度（Total Node Motion Fitness, TNMF）可表示為：

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

　　其中α1+α2+α3+α4+α5=1，單個αi的權值可根據外部啟發式算法［7］進行自適應調整。算法根據節點的運行情況在一定時間內進行多階段決策過程的優化處理，以最大限度取得單個αi的最優組合值為目標。

2節點部署遺傳算法

　　根據式（11），采用GA遺傳算子，可設計出節點的最優動態部署算法。本節將介紹節點重定位的染色體表示，以及算法的主要流程。

　　2.1染色體的表示

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

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

　　將染色體串的層次結構定義成：

　　((θ^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表示節點的移動矢量，并具有以下特性：

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

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

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

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

　　2.2算法的流程

　　算法的流程如圖2所示。

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

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

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

3算法仿真與結果分析

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

　　實驗模擬匯聚節點的運行，NS2軟件模擬網絡的流量。盡管每個GA適應度函數彼此存在競爭，但它們收斂于系統的平衡點，從而最大限度提高了網絡生存期，獲得了網絡的最佳覆蓋度。節點靜態和動態部署時，迭代次數與覆蓋度的函數關系如圖3所示。

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

　　迭代次數與節點損失之間的關系如圖4所示。從此圖可以看出，動態部署明顯優于靜態部署，損失的節點數減少15%～20%。在靜態部署情況下，節點的損失呈指數級，而在動態部署的情況下，由于總能量的分配更加優化，節點在簇內是逐漸消亡的。靜態部署方式下，節點的消亡會給覆蓋度帶來損失，由此會延長數據傳輸的路徑，增加數據傳輸的能耗。

4結論

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

參考文獻

　?。?］ 付華,韓爽.基于新量子遺傳算法的無線傳感器網絡感知節點的分布優化［J］. 傳感技術學報,2008,21(7): 1259-1263.

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

　?。?］ 黃月,項妹,肖磊,等. 無線傳感器網絡的節點部署問題研究［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.

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

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

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

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

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