WSN中基于雙群體差分進化的資源分配優化算法

郝曉辰，王立元，劉金碩，解力霞，張文煥

（燕山大學電氣工程學院，河北 秦皇島 066004）

1 引言

無線傳感器網絡（WSN,wireless sensor network）是由部署在監測區域內大量相互通信的傳感器節點形成的多跳自組織網絡[1]。隨著 WSN節點數目的不斷增加，節點受到的干擾以及鏈路之間的通信沖突也會隨之增強，這不僅會造成網絡容量下降，還會導致網絡中的節點由于數據重傳浪費能量。因此，如何進行合理地資源分配使網絡在降低干擾和避免通信沖突的同時，增加網絡容量、降低節點能耗成為亟待解決的問題。

傳統的資源分配都是單獨進行的，例如，文獻[2]研究了單獨的信道分配技術，其算法能夠明顯降低網絡的干擾。時隙分配問題也是當前研究的熱點問題[3～6]，時隙分配是避免通信鏈路沖突的最有效方法。但是單獨的信道分配或時隙分配都只能對網絡的某一方面性能進行優化，并且這種優化可能是在犧牲另一方面性能的基礎上的。基于這種考慮，許多研究者開始致力于資源分配聯合優化的研究，張治學等[7]考慮了信道分配與時隙分配對網絡性能的影響，提出了信道分配與時隙分配的聯合優化算法，但是該算法只是對以上2種算法的簡單疊加，并沒有真正考慮到它們之間的交互關系，這造成資源的嚴重浪費。文獻[8]在此基礎上考慮了信道分配與時隙分配之間的相互影響關系，采用優化的多信道分配機制，實現了時隙重用與信道數優化。文獻[9～12]都是對信道分配和功率控制進行了聯合優化，并在一定程度上對已有的工作做出了一些改進。文獻[13]提出了基于標準差分進化的信道分配與功率控制算法，然而該算法并沒有考慮節點能量的局限性，也沒有考慮可能存在的鏈路沖突對網絡造成的干擾。文獻[14]針對多信道多接口多跳的無線傳感器網絡提出了聯合擁塞控制、信道分配以及鏈路調度的算法。以上研究中并沒有一種算法是聯合研究信道分配、功率控制和時隙分配問題的，此外，以上研究都是把所求問題通過加權的方法轉化為單目標優化問題，使用這種方法得到的結果對權重的依賴性較大，權重因子的選擇往往就能決定結果的偏向。

基于上述分析，為提高多射頻多信道無線傳感器網絡的性能，提出了基于多目標優化模型的聯合資源分配算法，主要貢獻如下。

1) 綜合考慮了信道分配、功率控制以及時隙分配之間相互影響的關系，構建了系統的干擾模型和鏈路容量模型。

2) 以鏈路的干擾和沖突為約束條件，以減小能耗、增大網絡容量以及提高資源分配的均衡性為目標函數，構建了系統的資源分配多目標優化模型。多目標優化模型的建立突出了不同目標之間的權衡。

3) 采用雙群體差分進化算法對本文所構建的模型進行求解，并與使用標準差分進化算法的結果進行對比，實驗結果表明本文算法對提升網絡各方面的性能都有很大的改進。

2 干擾模型和鏈路容量

一般而言，節點的接口數目小于信道的個數，且節點的接口可以在各信道間進行切換。針對無線傳感器網絡的特點，本文有以下假設。

1) 節點的接口可以在各個信道及功率等級上進行切換，但在一個時隙內只能使用一個信道及一個功率等級。

2) 時隙的長度都是相同的，連續的時隙集合組成一個周期，成為幀結構，本文在研究過程中不考慮時隙的長短而只考慮時隙的個數對網絡性能的影響。

無線傳感器網絡用有向圖 G=(V,E)表示，其中，V表示節點集，E為邊集，設網絡中有N個節點，L條鏈路，則 V ={1,2,…,N},E={1 ,2,…,L},用Mi表示節點i的接口個數，任意一條鏈路eij∈E表示節點i到節點j的單向鏈路。網絡中信道集合用 C={1,2,… ,K }表示，K為可用信道的個數，所需的時隙集合用 R={1,2,… ,S }表示，S為最終為網絡分配的時隙個數，每條鏈路的可選功率范圍為是能夠使鏈路 eij正常通信的最小發射功率,根據信噪比定義[13]，可以得到滿足信噪比條件的鏈路 eij的最小發射功率為其中， hij是鏈路增益，α表示路徑損耗系數。 pmax(eij)是各節點的最大發射功率。只有當各鏈路的接收節點信噪比大于給定閾值時才能成功接收到消息，因此，本文用信噪比來描述鏈路受到的干擾強度大小，鏈路eij在信道 cij、時隙 rij中正常傳輸時，鏈路 eij的接收節點信噪比可表示為

根據香農容量公式，本文給出的鏈路容量計算式如式(3)所示，若鏈路eij在信道cij、時隙rij中的發射功率為pij，則鏈路eij的容量為

由式(3)可知，鏈路容量與信噪比的大小有關，信噪比越小，鏈路容量越小，進而網絡容量越小。

3 資源分配多目標優化模型

無線傳感器網絡在實際應用中一般都會涉及多個目標的同時優化，這些性能指標之間往往是相互聯系、相互制約的關系[15～17]。多目標優化問題一般可以轉化為單目標優化問題，但是轉化之后的單目標函數對權重的依賴性較大，權重設置稍有不當，就會對結果產生很大的影響。因此，為了避免設置權重，本文以鏈路的干擾和沖突為約束條件，以減小網絡能耗、最大化網絡容量、提高資源分配的均衡性為3個目標函數，構建了系統的資源分配多目標優化模型，如式(4)～式(8)所示。

在上述模型中，式(4)表示最小化網絡所有節點中最大的節點能耗，z(i)表示節點i在一個周期內的能耗，假設每個時隙的時間長度為t，時隙的個數為S，則節點在一個周期內的能耗可以表示為

其中，Neti(t)表示以節點i為發射節點的鏈路集合，Neti(r)表示以節點i為接收節點的鏈路集合。

式(5)表示最大化網絡容量。網絡容量在一定程度上反映了通信質量的好壞，為保證目標函數的一致性，將式(5)轉化為式(10)所示的最小化問題。

式(6)表示在各時隙內工作的所有鏈路的總容量的均衡性。若資源分配不均衡就會導致資源的浪費，甚至會出現網絡擁塞的情況，造成網絡通信時延。本文用各時隙內總容量的方差表示資源分配的均衡性。其中，W(r)表示處于第r個時隙的所有鏈路容量之和。

式(7)表示各節點的接口約束。由于各節點擁有的接口數量有限，且均小于正交信道的數量。有限的接口數量會使與節點關聯的鏈路共享同一接口，而一個接口上的2條鏈路是不能在同一時間段內進行傳輸的。其中，Link(i)表示節點i的所有通信鏈路集合，Mi表示節點i的接口個數。

式(8)表示干擾約束。為了不影響正常通信，網絡中的所有鏈路都應滿足信噪比條件，即γij≥γth。

4 基于雙群體差分進化的資源分配優化算法(RADEA)

雙群體差分進化算法是一種用于解決多目標優化問題的簡單高效的方法[18]。由于算法采用實數編碼，因此，應用到無線傳感器網絡中可以有效地提高復雜網絡系統的編碼效率和運算速度。雙群體差分進化算法迭代過程中分為2個種群的進化，一個是同時滿足網絡中所有節點的接口約束和干擾約束的占優可行解種群popf，反之，另一個是占優不可行解種群popc。popf還具有一定的記憶功能，lbest用于記憶popf中每一個個體搜索到的最優可行解，gbest用于記憶popf到目前為止搜索到的最優可行解，是外部存檔集。算法的主要步驟包括個體編碼及種群初始化、種群的變異和交叉、個體的選擇與種群的更新。

4.1 個體編碼及種群初始化

由于本文的資源分配是基于鏈路的，假設網絡中的鏈路數量為L，則個體矩陣的維數為 3×L。任意一個個體的編碼可以表示為

在進行種群初始化時，在信道、功率、時隙的可選范圍內隨機生成初始個體，每生成一個個體都要根據節點接口約束和鏈路干擾約束判斷該個體的可行性，將可行解插入種群popf中，將不可行解插入種群popc中，一直循環，直到popf和popc都滿足給定的種群規模N1、N2。

4.2 種群的變異和交叉

本文算法給出了2種變異策略，其中，策略1的目的在于通過向較優個體學習，改善算法的收斂速度。策略2的目的在于和不可行解進行信息交流，共享不可行個體的一些優良特性，增加資源分配方案群體的多樣性。2種變異策略分別如式(13)和式(14)所示。

其中，Q(r1)是對應于popf中第r1個資源分配方案個體經過變異操作產生的實驗個體，而其他為r2、r3、r4、r5的個體都是從對應集合中隨機選擇的有差異的個體。

算法中的交叉操作采用均勻的交叉方式，將資源分配方案個體矩陣的每列都作為一個交叉點，即每一條鏈路都是一個交叉點。如式(15)所示，Pj是針對實驗個體Q(r1)中的第j列產生的位于區間[0,1]中的隨機數，Cr是給定的參數。

實驗個體G(r1)的變量范圍可能會超出本文規定的信道、功率及時隙的可選范圍，這時需要對G(r1)中違反約束的元素進行邊界條件處理[19]，并將處理后的個體記作son(r1)。

獨立后的實驗教學，利用實驗室等實驗條件并按照實驗教學大綱的質量要求和學時要求全部實施完成，其開出率便可得以保證。

4.3 個體的選擇與種群的更新

定義1 任意2個個體r1和r2，若r1和r2同時滿足式(16)和式(17)，則稱r1支配r2，記作r1 ?r2。

首先，判斷子代種群son中個體的可行性，并將可行解和不可行解分別插入popf和popc中。然后，判斷popf和popc中任意2個個體之間的支配關系，刪除被支配個體，當種群規模達到N1、N2時停止判斷。若刪除所有被支配個體后種群規模依舊大于N1、N2，則計算個體的擁擠度[20]并將擁擠度小的個體刪除以保證種群規模不會發生變化。

4.4 最佳均衡解

為了從pareto解集中選出一個最佳均衡解，本文為每個目標函數（fi）定義線性隸屬度函數，如式(18)所示，其中，i= 1 ,2,3，將集合gbest中的每一個支配解（g）代入目標函數（fi）中，即可得到目標函數（fi）對應的最大值（）和最小值（）。

由式(18)可知，支配解個體對應的隸屬度函數值越小表明目標函數實現的程度越強。對于gbest中的每一個支配解（g），定義聚合度函數如式(19)所示，聚合度函數表示支配解（g）對應的所有目標函數的隸屬度之和，其中，m表示目標函數的個數，本文取m=3。

式(19)表明，聚合度函數值最小的個體就是本文要求的最佳均衡解。

4.5 算法步驟

綜上所述，算法步驟概括如下。

Step1 為變異因子F、交叉概率Cr、迭代次數mmax、可行解種群規模N1和不可行解種群規模N2設初值。按4.1節所述產生初始種群popf、popc，并初始化lbest、gbest。

Step2popf中的個體經策略1或策略2的變異操作和式(15)所示的交叉操作后產生實驗種群G。

Step3 對實驗種群G中超出范圍的元素進行邊界條件處理產生子代種群son。

Step5 如4.3節所述更新popf和popc。

Step6 根據可行性與支配關系更新lbest。若son(r1)是可行解，則判斷son(r1)是否支配于lbest(r1)，若son(r1)支配對應的個體lbest(r1)，則用son(r1)替換lbest(r1)，否則，不予替換；若son(r1)是不可行解，則lbest(r1)不更新。gbest屬于外部存檔集，按照 SPEA[21]中的方法更新gbest。m=m+1。

Step7 判斷m≤mmax是否成立，若成立轉Step2，否則，轉Step8。

Step8 輸出最優解集gbest。

Step9 根據線性隸屬度函數和聚合度函數選出一個最佳均衡解。

5 仿真分析

本節在 Matlab環境下首先對算法中的參數進行仿真，然后通過對比實驗對本文算法進行分析。

實驗 1 為了選出合適的變異因子和交叉概率，首先對變異因子F和交叉概率Cr進行仿真實驗。已知網絡拓撲如圖1所示，圖1標號表示節點號，給定的網絡節點數為25，鏈路數為24，其中箭頭表示節點間通信的單向鏈路。在給定的拓撲圖上，采用不同的變異因子和交叉概率組合運行本文算法，每組參數運行30次并取平均值，仿真結果如圖 2所示。圖 2(a)表示不同變異因子F和交叉概率Cr對各時隙負載均衡性的影響。圖 2(b)和圖 2(c)分別表示不同參數對節點能耗和網絡容量的影響。實驗1中其他參數設置如表1所示。

圖1 網絡拓撲

圖2 不同參數對網絡性能的影響

表1 仿真參數

通過對圖2(a)的分析發現，當Cr=0.1、Cr=0.5和Cr=0.7時負載均衡性較好，但是由圖2(b)可知，Cr=0.1時節點的能耗過大。此外，網絡容量和負載均衡性都隨F的增大而變差。綜合考慮網絡性能隨F和Cr的變化，得到4組參數：F=0.1,Cr=0.5；F=0.1,Cr=0.7；F=0.4,Cr=0.5；F=0.4,Cr=0.7，如圖 3 所示。由圖3可知，F=0.1時算法收斂速度較快，并通過對F=0.1,Cr=0.5和F=0.1,Cr=0.7這2組參數對網絡性能的分析可知，F=0.1,Cr=0.5時得到的各時隙負載均衡性和網絡容量與F=0.1,Cr=0.7時得到的結果相差不大，但是由圖 3(b)可知,F=0.1,Cr=0.7時的節點能耗遠遠大于F=0.1,Cr=0.5時的能耗。所以確定最終的參數為F=0.1,Cr=0.5。

圖3 不同參數對收斂速度的影響

實驗 2 基于標準差分進化的資源分配優化算法[14]研究了功率控制與信道分配的聯合分配問題，將文獻[14]的算法和基于潛在博弈的功率控制和信道分配優化算法進行對比分析，仿真結果表明該算法在一定程度上降低了網絡干擾，增大了網絡容量。為了驗證本文算法的性能，將本文算法與基于標準差分進化的資源分配算法進行對比，并將迭代次數設置為1 000次，其他實驗參數與實驗1相同，得到的信道分配和時隙分配結果如圖4所示，各時隙內的負載均衡性如圖 5所示。各鏈路干擾、各信道平均干擾和網絡容量對比分別如圖6～圖8所示。

圖4 信道分配和時隙分配結果

圖5 各時隙負載均衡性

圖6 各鏈路干擾

圖7 各信道平均干擾

圖8 網絡容量對比

圖 4和圖 5分別表示本文算法運行的最終結果，圖4中，處于不同時隙的鏈路用不同的符號標記，而鏈路上的數字表示該條鏈路通信所用的信道，由圖4可以看出，得到的結果有效地避免了鏈路的通信沖突，最終整個網絡所用時隙個數為 5個，且處于各時隙內的鏈路條數分別為5條、5條、4條、5條、5條，處于各信道內的鏈路條數分別為4條、3條、6條、5條、6條，結合圖5，更能體現出資源分配的均衡性。

由圖6可知，RADEA使各鏈路受到的干擾更加均衡，且接近于 0，由于標準差分進化算法并沒有考慮時隙對干擾的影響，因此，使用標準差分進化算法得到的干擾大于 RADEA，且使用標準差分進化算法得到的干擾具有較強的波動性，同理，由圖6中各信道內的平均干擾也可以看出，RADEA的抗干擾性更強。

由圖7可知，由于RADEA得到的鏈路干擾要小于使用標準差分進化算法得到的鏈路干擾，所以，本文算法得到的網絡容量遠遠大于使用標準差分進化算法的網絡容量。

6 結束語

本文通過考慮時隙、信道和功率的交叉影響，首先建立了系統的資源分配多目標優化模型，然后在所建立的模型的基礎上，提出了基于雙群體差分進化的資源分配優化算法 RADEA，仿真結果表明RADEA能夠有效地解決由于鏈路沖突和干擾過大而導致的能耗過大、容量受限和資源分配不均衡的問題。

參考文獻：

[1]任豐源,黃海寧,林闖. 無線傳感器網絡[J]. 軟件學報,2003,14(7):1282-1291.REN F Y,HUANG H N,LIN C. Wireless sensor network[J]. Journal of Software,2003,14(7):1282-1291.

[2]HAO X C,RU X Y,LI X D,et al. Energy efficient based channel assignment game algorithm for wireless sensor network[J]. Wireless Personal Communications,2014,85(4):2749-2771.

[3]SINEM C E,PRAVIN V. TDMA scheduling algorithms for wireless sensor networks[J]. Wireless Network,2010,16(4):985-997.

[4]XU X H,LI X Y,SONG M. Efficient aggregation scheduling in multi-hop wireless sensor networks with SINR constraints[J]. IEEE Transactions on Mobile Computing,2013,12(12):2518-2527.

[5]SHASHIDHAR G,MILIND D,RAVI P. Link scheduling in wireless sensor networks: distributed edge coloring revisited[J]. Journal of Parallel and Distributed Computing,2013,68(8):1122-1134.

[6]AL-ZAHRANI A Y,YU F R. An energy-efficient resource allocation and interference management scheme in green heterogeneous networks using game theory[J]. IEEE Transactions on Vehicular Technology,2016,65(7):5384-5396.

[7]張治學,曾波,張各各.基于多信道的能量高效傳感器節點調度算法[J]. 計算機工程,2015,41(9): 135-139.ZHANG Z X,ZENG B,ZHANG G G. Energy efficient sensor node scheduling algorithm based on multiple channels[J]. Computer Engineering,2015,41(9):135-139.

[8]ABUSAYEED S,XU Y,LU C Y,et al. Distributed channel allocation protocols for wireless sensor networks[J]. IEEE Transactions on Parallel and Distributed Systems,2014,25(9):2264-2274.

[9]SONG Y,ZHANG C,FANG Y G. Joint channel and power allocation in wireless mesh networks: a game theoretical perspective[J]. IEEE Journal on Selected Areas in Communications,2015,26(7):1149-1159.

[10]HAO X C,GONG Q Q,HOU S,et al. Joint channel allocation and power control optimal algorithm based on non-cooperative game in wireless sensor networks[J]. Wireless Personal Communications,2014,78(2):1047-1061.

[11]HAO X C,RU,X Y,LI X D,et al. Joint game algorithm of power control and channel allocation considering channel interval and relay transmission obstacle for WSN[J]. Wireless Personal Communications,2015,86(2):521-548.

[12]郝曉辰,鞏倩倩,侯爽,等.無線傳感器網絡中支持并行傳輸的信道與功率聯合優化博弈算法[J]. 電子與信息學報,2014,36(7):1720-1727.HAO X C,GONG Q Q,HOU S,et al. Joint channel and power optimal game-theoretic algorithm for concurrent transmission in wireless sensor network. Journal of electronics & information technology[J].Journal of Electronics and Information Technology,2014,36(7):1720-1727.

[13]賈杰,李燕燕,陳劍. 認知無線網狀網中基于差分演化的功率控制與信道分配[J].電子學報,2013,41(1): 62-67.JIA J,LI Y Y,CHEN J. Channel allocation and power control based on differential evolution algorithm in cognitive radio mesh network[J].Acta Electronica Sinica,2013,41(1):62-67.

[14]MERLIN S,VAIDYA N,ZORZI M. Resource allocation in multi-radio multi-channel multi-hop wireless networks[C]//27th IEEE Conference on Computer Communications (INFOCOM 2008). 2008:1283-1292.

[15]BAGHAEE H R.,MIRSALIM M,GHAREHPETIAN G B,et al.Security /cost-based optimal allocation of multi-type FACTS devices using multi-objective particle swarm optimization[J]. Simulation-Transactions of the Society for Modeling and Simulation International,2012,88(8):999-1010.

[16]WANG L F,SINGH C. Environmental / economic power dispatch using a fuzzified multi-objective particle swarm optimization algorithm[J]. The Electric Power Systems Research,2007,77(12):1654-1664.

[17]BAGHAEE H R,MIRSALIM M,GHAREHPETIAN G B. Reliability/cost-based multi-objective pareto optimal design of stand-alone wind/PV/FC generation microgrid system[J]. Energy,2016,115(15):1022-1041.

[18]孟紅云,張小華,劉三陽. 用于約束多目標優化問題的雙群體差分進化算法[J].計算機學報,2008,31(2):228-235.MENG H Y,ZHANG X H,LIU S Y. A differential evolution based on double populations for constrained multi-objective optimization problem[J]. Chinese Journal of Computers,2008,31(2):228-235.

[19] 周輝仁,唐萬生,王海龍. 基于差分進化算法的多旅行商問題優化[J]. 系統工程理論與實踐,2010,30(8):1471-1476.ZHOU H R,TANG W S,WANG H L. Optimization of multiple traveling salesman problem based on differential evolution algorithm[J].System Engineering Theory & Practice,2010,30(8):1471-1476.

[20]DEB K,PARTAP A,AGARWAL S,et al. A fast and elitist multiobjective genetic algorithm: NSGA-II[J]. IEEE Transactions on Evolutionary Computation,2002,6(2):182-197.

[21]ZITZLER E,THIELE L. Multiobjective evolutionary algorithms: a comparative case study and the strength pareto approach[J]. IEEE Transaction on Evolutionary Computation,1999,3(4):257-271.