WSN路由節點優化分布設計的免疫克隆算法

江 楠， 徐 秦

(中國人民解放軍92124部隊， 遼寧 大連 116023)

WSN路由節點優化分布設計的免疫克隆算法

江 楠， 徐 秦

(中國人民解放軍92124部隊， 遼寧 大連 116023)

對于無線傳感器網絡(WSN)路由節點的優化分布設計，人工免疫進化算法存在幾何選擇區域局限，為了緩解此問題，避免系統收斂于局部最優解，提出一種基于免疫克隆算子的設計方案。根據WSN節點覆蓋原理，構建WSN路由節點自適應人工免疫分布模型，用免疫平衡機理計算染色體在每個節點部署網格中的信息濃度概率，采用克隆檢測算法監測WSN網絡中節點冗余濃度，以使每個WSN路由節點輻射信息素最大化，突破幾何選擇區域的限制，實現最優節點部署和覆蓋。仿真實驗表明，新算法能提高網絡連通性和節點利用率。

無線傳感器網絡；路由節點；分布；免疫算法

無線傳感器網絡(Wireless Sensor Network, WSN)是一種利用分布式路由節點將數據傳送到決策中心，從而感知和采集節點所處環境的數據信息的網絡結構。WSN的路由節點分布設計決定著其生存周期和對環境信息的感知能力，優化智能的路由節點分布設計算法不但可以使WSN能自主感知實現數據信息的傳遞和決策，提高網絡的連通性，而且能降低節點能耗，提高WSN網絡系統的可靠性和穩定性，因此研究WSN路由節點的優化部署和分布設計算法具有重要的意義。

WSN的路由節點的優化部署和分布設計算法包括空間幾何設計和智能優化遺傳設計兩個主要方面。文獻[1]采用WSN多傳感器融合處理辦法實現對WSN節點的定位檢測，分析實現WSN網絡路由節點的分布設計，其控制算法采用粒子濾波算法實現節點自動控制，導致對WSN簇頭節點分布控制效能限制較大，WSN節點分布準確度有待提高；文獻[2]對WSN的通信協議進行了簇內節點優化設計，有效排除了惡意節點，從而實現對WSN節點的分布設計，但算法采用多重節點反復組合的方法進行WSN路由節點分布設計，導致節點利用效率不好；文獻[3]中提出了一種基于相鄰節點WSN節點分布信任值提取算法，實現對WSN數據的融合和分布覆蓋優化，結合自組織神經網絡系統，實現WSN節點定位，但算法在低信噪比和單接收節點調制中對WSN節點準確定位困難，導致WSN網絡節點冗余，增大開銷[4]；文獻[5]采用粒子群進化算法進行路由節點分布設計，由于粒子群在進化迭代中免疫平衡算子存在幾何選擇區域的局限性，系統易收斂于局部最優解[6-10]。

本文基于免疫克隆算子提出一種WSN網絡路由節點優化分布設計方案，并借助仿真實驗驗證新算法的性能。

1 WSN網絡路由節點分布設計

1.1 WSN網絡路由節點分布構建原理

首先研究WSN網絡路由節點優化分布設計的原理，進行無線傳感器網絡節點分布設計的基本構建。對于在無線傳感器網絡中的每一個節點，有其自身的輻射半徑，在輻射半徑之外而又不能被其它網絡節點輻射的為輻射盲區。因此，在對進行無線傳感器網絡組網中，要有效利用網絡節點，實現資源分配最大化，網絡覆蓋最優化。節點均勻分布的傳感器網絡節點分布模型示意圖如圖1所示。

圖1 節點均勻分布的傳感器網絡節點分布模型

在圖1中，無線傳感器網絡路由節點假設為Z，該節點的輻射或稱為覆蓋半徑為RZ，RZ為以Z為圓心的覆蓋圓的半徑，在該半徑圓內，為有效覆蓋區，能進行有效的通信覆蓋。因此，與節點Z任意相鄰的節點與保證在其信息發散區域內，需保證信息的有效傳輸和通信，對于節點Z的鄰接節點，要按照特有和一定的順序和方式進行排列組合，確保信息最優覆蓋。在傳統模型中，WSN網絡中節點不得不頻繁收集新的網絡拓撲信息、重新計算調度方案并傳送給每個節點，這將會消耗大量的能量，以致傳統的數據集中式算法在實際應用過程中效率很低，無法實現有效準確和實時的信息采集和拓撲分析。

1.2 WSN路由節點系統模型構建

假設WSN有N個節點，節點同步分布實現對環境條件的監測和信息特征提取，路由節點均勻的分布在監測區域Ωη，分布模型如圖1表示,其中節點分布網格中每兩個節點之間的最小距離為d。根據節點類型，在網絡模型中，節點分為Sink節點、監測點、傳感器節點和無節點等類型，該模型采用四元組結構表示，以自頂向下的方式分層構造數據聚集樹，優化節點分布設計，其目的在于以數量最少的連接節點將相距兩跳的支配節點連接起來，形成一棵根在Sink節點的數據聚集樹DAT。具體來說，在數據聚集樹的構造過程中，假設Sink節點以數量最少的連接節點將相距兩跳的支配節點連接起來，形成一棵數據聚集樹后，則對于數據聚集樹上某一支配點，只要將與之相距兩跳、尚未加入數據聚集樹的支配節點加入到數據聚集樹。例如，假設有相距兩跳的兩個支配節點u和v，如果支配節點u先將與之相距兩跳、尚未加入數據聚集樹的支配節點加入到數據聚集樹，則對于支配節點v，只要將D2(v)-D2(u)∩D2(v)中的點加入到數據聚集樹即可，這是因D2(u)∩D2(v)中的支配點已通過支配節點u加入到數據聚集樹。

支配節點u加入位置為ηn∈Ωη(n=1,2,…,N)，支配節點u先將與之相距兩跳覆蓋，得到每一個節點與進化算子中最優子節點位置相關的數據為x(ηn)，定義節點密度來表征分布節點覆蓋點集的相關性為

E[x(ηp)x(ηq)]=ρ‖ηp-ηq‖,

(1)

其中ρ∈(0,1)表示Sink節點連通性代價系數，通過節點代價系數檢測已覆蓋的傳感器節點，得到相應的空間相關系數，對WSN的已覆蓋節點進行數據融合傳遞，WSN網格中心節點收到的節點數據信息素為

(2)

(3)

根據構建的WSN路由節點系統模型，以下分析WSN網絡路由節點優化分布設計。

2 路由節點分布算法與優化實現

2.1 自適應人工免疫節點分布算法

WSN網絡路由節點分布設計，旨在按照一定的節點排列方法，以最為經濟的網絡節點實現最大覆蓋率的輻射區域，從而完成傳感器節點信號覆蓋的最優化。構建評價指標體系，評價傳感器節點優化覆蓋的性能，對研究傳感器節點優化覆蓋算法具有檢測和評估價值。WSN節點在尋優最優位置信息的時候，可通過模擬生物進化的人工免疫行為，實現信息位置的最佳匹配。在此給出自適應人工免疫節點分布算法。

假設融合中心有各傳感器節點得到的數據y=(y1,y2,…,yN)T，采用粒子群局部搜索算法，得到目標節點信息偏差x(η)(η∈Ωη)，節點覆蓋區域抗體濃度評價均方誤差(Mean Squared Error， MSE)估計值為

(4)

(5)

其中

rη=E[x(η)xs],

xs=(x(η1),x(η2),…,x(ηN))T,

(6)

(7)

(8)

其中γ0表示單位區域的信噪比。

采用目標免疫的方法，對WSN節點進行目標免疫克隆節點伴隨指導，可突破節點尋優過程中對空間區域的限制。

采用自適應人工免疫節點分布算法進行WSN節點分布設計的流程可描述為：首先用染色體所求的節點更新信息素解，把這些所需的解組成一個初始群體并放置在這個集合的環境中；然后計算每個個體的適應度，淘汰適應度較低的小集群，復制高適應度的個體，按照設定概率進行交叉和變異兩種基因操作；最后通過以上步驟產生出的新個體就是所有樣本種群的下一代。這樣不停的進化，下一代比上一代更優，適應度更高，最后結果會收斂到一個最優的個體上，所需求解問題的最優解就是這個最優的個體。

具體的計算準備流程包括：(1)確定計算方案，即確定無線傳感器網絡節點的整個搜索空間的計算方式。(2)確定適應值的范圍，即通過一個適應度函數來對小集群群體中的每個特征量的適應度進行計算。(3)確定參數和變量在控制算法的選取，即選取小集群種群的規模M、最大代數N、交叉概率Pc和變異概率Pm等參數。(4)確定算法的收斂的標準，以達到結束或者進行結果判斷實現最佳搜索和信息的覆蓋。

算法流程如圖2所示。

圖2 自適應人工免疫節點分布算法流程

根據傳統的分布設計算法中，變異交叉執行算子在進化迭代中免疫平衡算子存在幾何選擇區域的局限性，系統易收斂于局部最優解，因此需要對算法進行改進。

2.2 算法改進與優化實現

引入免疫克隆算子，對傳統的人工免疫進化WSN節點分布設計算法進行改進。

基于WSN節點覆蓋原理，構建WSN網絡路由節點自適應人工免疫分布模型，用免疫平衡機理計算染色體在每個節點部署網格中的信息濃度概率，表示為

(9)

采用克隆檢測算法監測WSN網絡中節點冗余濃度，在此引入克隆變異算子，優化節點信息素迭代更新過程，克隆變異算子為

(10)

此時每個WSN路由節點輻射信息素為

(11)

即采用最大似然估計，得到克隆檢測算法估計出每個WSN路由節點輻射最大信息素。監測WSN網絡中節點冗余濃度，使每個WSN路由節點輻射信息素最大化，從而可有效突破幾何選擇區域的限制，實現最優節點部署和覆蓋，得到改進后的覆蓋半徑下節點密度對MSE的影響

(12)

3 仿真實驗與結果分析

仿真實驗以100 m × 100 m二維平面監測區域為研究對象進行，WSN網絡路由節點通過免疫克隆優化迭代的實現最優節點分布，其中，仿真平面為正方形二維平面，該二維平面為無線傳感器網絡節點拓撲覆蓋研究區域。免疫群初始的群體個數即隨機分布的傳感器節點個數假設為n=100, 交叉概率Pc取值為0.40～0.99，變異概率Pm一般定為0.05。仿真實驗中，對克隆檢測算子進行免疫平衡設計，在仿真過程中對相關數據，比如覆蓋率、覆蓋度、傳感器節點個數進行了詳細記錄。根據迭代，最后確定最佳迭代次數選擇為N=300。在待檢測覆蓋區域W中，假設需要設置Q同等性能指標的節點，各個傳感節點在區域W中的坐標參數假設為(xi,yi)，各個傳感節點由于性能參數相同，故而其覆蓋半徑是相同的，這里假設為r，設定網格大小為24，網絡規模為20×20，采用改進算法和傳統方法對WSN網絡路由節點設計中節點密度與空間相關性以及信息素飽和度之間的關系進行仿真。在WSN網絡中不同節點數量下得到節點密度對節點信息素飽和度均方根誤差MSE關系如圖3所示。可見，MSE隨節點密度單調遞減，節點密度越高，空間相關性就越強，則估計精度越高。而采用改進方法，節點分布飽和度更大，更能有效逼近最優值，網絡連通性更好。

(a) 傳統方法

采用改進方法仿真得到最優節點密度隨節點數變化關系如圖4所示。可見，采用改進方法能快速實現最優節點密度設計，收斂性好，能在最少節點下實現節點分布和信息傳輸最優，這說明采用改進算法進行WSN路由節點分布設計，網絡連通性和節點利用率都將獲得大幅度提高。

圖4 最優節點密度隨節點數變化關系

4 結 語

針對WSN網絡路由節點分布優化設計的問題，提出一種引入免疫克隆算子的WSN網絡路由節點優化分布設計方案，基于WSN節點覆蓋原理，構建WSN網絡路由節點自適應人工免疫分布模型，用免疫平衡機理計算染色體在每個節點部署網格中的信息濃度概率，采用克隆檢測算法監測WSN網絡中節點冗余濃度，使每個WSN路由節點輻射信息素最大化，研究得出，采用該算法進行WSN路由節點分布設計，節點信息素飽和度高，WSN連通性和節點信息覆蓋性較好。

[1] 龔娟,段樹華.PSO算法和神經網絡的入侵檢測系統設計[J].計算機測量與控制,2010,18(8): 1924-1927.

[2] 楊建華,王龍飛.基于FPGA的交通流量視頻檢測系統設計[J].計算機與數字工程,2013,41(11): 1811-1813.

[3] 董慧慧,郭亞軍.一種基于節點多角度信任的無線傳感器網絡[J].計算機科學,2009,36(9):43-45.

[4] 趙娟,趙薔,吳粉霞.基于自組織映射神經網絡的圖像檢索算法[J].科技通報,2013,29(2):55-57.

[5] 楊海霞.基于改進數據過濾算法的異構數據庫優化挖掘技術[J].科技通報,2013,29(6):125-127.

[6] 朱珍.基于神經網絡集成分類器預處理的支持向量機分類算法[J].科技通報,2013,29(4):26-30.

[7] 吳光榮,柳書濤,章劍雄.基于ZigBee的無線傳感器網絡數據管理平臺[J].電子科技,2009,22(2):64-67.

[8] 劉家亮,王海燕,姜喆,等.垂直線列陣結構對PTRM陣處理空間增益的影響[J].魚雷技術,2010, 18(4):263-267.

[9] 韋然.無線傳感器網絡節點的設計與實現[J].電子科技,2012,25(1):31-35.

[10] 梁青,熊偉,韓昊澎.各向異性無線傳感器網絡DV-Hop算法性能仿真[J].西安郵電大學學報,2013,18(5):31-36.

[責任編輯:王輝]

WSN routing node distribution design based on immune clone pptimization

JIANG Nan, XU Qin

(Unit 92124 of PLA, Da lian 116023, China)

For WSN to optimize the design of the distribution of routing nodes, the artificial immune evolutionary algorithm has limitation of geometry selected area limits, thus lead system converges to local optimal solution. An improved immune clone algorithm is proposed in this paper. According to the principle of WSN node coverage, an adaptive artificial immune WSN routing nodes distribution model is built. The information probability of concentration of chromosome is calculated by the immune balance mechanism in each node deployment in the grid. WSN nodes redundant concentration in network is monitored by using the clone detection algorithm. Each WSN routing node radiation pheromones is therefore maximized to breakthrough the limitation of geometry selected area and to realize the optimal node deployment and coverage. Simulation experiments show that the new algorithm can improve the utilization rate of network connectivity and node.

wireless sensor network, routing node, distribution, immune algorithm

10.13682/j.issn.2095-6533.2014.05.015

2014-06-10

江楠(1982-)，女，碩士，助理工程師，從事通信工程研究。E-mail：66757588@qq.com 徐秦(1972-)，女，高級工程師，從事通信工程研究。E-mail:ariaxu@hotmail.com

TN 926; TP 212

A

2095-6533(2014)05-0077-05