基于進化多目標合作博弈的體域網通信優化

周 暉，錢蘭美，薛 磊，王曄嬌

(南通大學 電子信息學院，江蘇 南通 226019)

0 引 言

在基于云計算的體域網(cloud-body sensor network，CBSN)[1,2]中，云計算的效用計算、虛擬化技術、數據存儲等優勢使大規模感知數據的實時獲取成為可能，研究云計算與體域網之間的數據通信是其關鍵技術[3,4]。由于傳感器節點能量有限、通信帶寬受限，使獲取大規模感知數據與降低通信帶寬占用量和傳感器節點能耗相沖突[5]。

目前，主要有兩類解決方案。一類是采用多目標進化算法[6,7]。文獻[8,9]采用選擇、交叉、變異等遺傳算子實現種群進化，通過非支配排序法與擁擠度比較算子，最終得到Pareto解集，仿真結果顯示該方法能獲得質量好的解，但解的分布不均勻、不穩定，且在尋優后期收斂速度較慢，計算成本較高。另一類是采用非合作博弈方法[10]。文獻[11]采用演化博弈算法(evolutionary game algorithm，EGA)，利用目標間約束支配關系決定優勝者，同時采用復制者動態和進化穩定策略最終達到Nash均衡狀態，仿真實驗將其與NSGA-II[12]相比較，在優化性能和穩定性方面均優于NSGA-II。然而，在博弈過程中由于競爭過于激烈易導致部分質量好的解丟失，甚至陷入局部次優，另外非合作博弈具有目標偏好，不能實現整體目標利益的均衡。

針對上述問題，提出CBSN的進化多目標合作博弈方法(sensor cloud-evolutionary multi-objective cooperative game，SC-EMCG)。根據目標之間的競爭與合作關系構造收益函數，進行共謀合作博弈，在競爭中開展合作，在各個沖突目標之間互相權衡、競爭，以實現目標整體收益的最大化；同時結合進化計算，引入精英保留策略，將博弈獲勝方復制到種群中，落敗方被移除種群；引入Levy飛行算子，擴大種群搜索范圍，避免陷入局部次優。

1 CBSN博弈模型

針對圖1中的CBSN通信架構，建立數據量、通信帶寬和傳感器節點能耗三者之間的博弈模型。

圖1 CBSN通信架構

1.1 符號列表

與CBSN通信問題相關的基本符號說明見表1。

表1 基本符號說明

1.2 博弈方與博弈策略集

博弈方為相互沖突的3個目標，包括云端數據量、通信帶寬占用量和傳感器節點能耗。博弈策略集s(bi)為決策變量的組合，如式(1)所示

(1)

1.3 收益函數

在CBSN博弈模型中，各博弈方的收益函數即為其適應度函數，分別是傳輸層和云服務層之間的通信帶寬占用量，物理傳感器的能量消耗，云服務層數據收益。

帶寬占用量收益函數fB：傳輸層和云層之間單位時間內傳輸數據總量

式中：第1項為傳輸層與云服務層單向push通信帶寬占用量；第2項為傳輸層與云服務層雙向pull通信帶寬占用量；dr為常量，表示云層向傳輸層之提出一個pull請求的大小。

能耗收益函數fE：在時間窗口W內傳感器節點進行數據傳輸消耗總能量

數據量收益函數fY：云應用為用戶收集的數據總量

(4)

1.4 約束條件

在CBSN中，博弈過程的約束條件如下

約束1：fE

(5)

約束2：fY

(6)

其中，cE是能量消耗fE的上界，cY是數據受益fY的下界。

2 SC-EMCG算法

2.1 合作博弈收益函數的構造

根據各博弈方之間的競爭與合作關系，構造各博弈方的收益函數

(7)

2.2 共謀合作博弈步驟

根據式(7)構造的收益函數進行共謀合作博弈，具體博弈步驟見流程如圖2所示。

圖2 共謀合作博弈流程

在生成初始策略組合后，各博弈方在自身策略空間,以自身收益函數為目標進行單目標優化，得到最佳策略組合，再根據約束條件以及前后策略組合之間的范數是否滿足收斂準則確定其是否可行。

2.3 進化計算

SC-EMCG算法將合作博弈與進化計算相結合。進化算子包括Levy飛行算子[13]與精英保留策略。初始化策略空間后，采用Levy飛行算子進行位置更新。其實現如下

(8)

其中，α>0是搜索步長，通常令α=1；符號⊕表示點對點乘法。Levy飛行的隨機步長滿足Levy分布，即Levy～u=t-λ, (1<λ≤3)，采用Levy飛行可擴大算法的搜索范圍，促進全局收斂。

采用精英保留策略[14]，父代種群與子代種群共同參與下一代種群的進化，以加快算法執行速度，保證種群多樣性。

2.4 算法流程

SC-EMCG算法流程如圖3所示。

圖3 SC-EMCG算法流程

SC-EMCG算法將共謀合作博弈與進化計算相結合，其合作博弈收益函數的構造見式(7)；共謀合作博弈過程見2.2節；Levy飛行策略進行位置更新，其飛行步長滿足heavy-tailed分布；精英保留將獲勝方復制到種群中，將落敗方移除種群。

3 仿真研究

為了驗證SC-EMCG算法在求解CBSN通信優化問題的性能和計算效率，分別從收斂結果、收斂速度、解的穩定性和解的多樣性4個方面進行研究。并將其與多目標進化算法NSGA-II和非合作博弈中的EGA比較。為保證實驗的公平性，NSGA-II、EGA與SC-EMCG的基本參數設置相同。仿真實驗采用Matlab7.8實現，運行在3.10 GHz Core i5-2400CPU，4 GBRAM的計算機上。

3.1 仿真場景及參數設置

建立一個遠程監控10個病人生理活動的仿真環境，每個病人攜帶一個sink節點，佩戴5種傳感器，組成一個單跳身體傳感網絡。在時間周期3小時內云端提出10 000個數據請求，請求均勻分布在虛擬傳感器節點上，傳感器節點參數見表2，仿真參數見表3。根據帶寬占用量，傳感器節點能耗以及數據量三者之間的競爭與合作關系，令wii服從正態分布ω11～(0.75,0.005)，ω22～(0.5,0.005)，ω33～(0.5,0.005)。

3.2 仿真結果與分析

收斂結果分析。圖4(a)，圖4(b)，圖4(c)分別是算法SC-EMCG、EGA和NSGA-II數據量、節點能耗和帶寬占用量收益函數的收斂曲線。由圖4可知，SC-EMCG算法的數據量、節點能耗和帶寬占用量，均優于NSGA-II；當迭代次數比較小時，算法SC-EMCG優化性能略低于EGA算法，但隨著迭代次數的增加，SC-EMCG算法的收斂結果明顯優于EGA算法。

表2 傳感器節點參數設置

表3 仿真參數設置

圖4 收益函數收斂曲線

表4為3種算法各個收益函數的最優值、平均值和最劣值。由表可見，無論是最優值、最劣值、平均值，SC-EMCG算法得到的數據量、帶寬占用量和節點能耗均優于算法NSGA-II和EGA。由圖4和表4所列出的仿真結果可見，SC-EMCG算法有效實現數據量、通信帶寬和傳感器節點能耗三者之間的均衡。

收斂速度分析。表5為SC-EMCG、EGA和NSGA-II這3種算法的運行時間，由表5可知，在迭代次數小于100時，3種算法運行時間相差不大。但是，在100代之后，算法SC-EMCG和EGA運行時間明顯優于NSGA-II算法，SC-EMCG算法的整體運行時間比MOEA快18.4%。由此可見，NSGA-II在算法前期收斂速度較快，但在算法后期收斂速度較慢；而算法SC-EMCG和EGA一直保持較快的收斂速度。

解的分布性分析。圖5(a)，圖5(b)，圖5(c)分別為算法SC-EMCG、EGA和NSGA-II所有個體在三維目標空間的映射。由圖5可見，SC-EMCG算法解的分布集中，且均勻；EGA算法次之；而NSGA-II算法的解分布比較分散，不均勻。可見，SC-EMCG算法解的分布性好。

表4 收益函數值

表5 SC-EMCG、EGA和NSGA-II運行時間

圖5 三維目標空間分布

解的多樣性分析。通過Hypervolume指標[15]衡量解的多樣性，指標數據進行歸一化處理。圖6為3種算法的Hypervolume值。由圖6所示，SC-EMCG算法的Hypervolume值顯著優于其它兩種算法，可見，SC-EMCG算法的種群多樣性優于其它兩種算法，反映該算法在避免局部次優，實現全局收斂方面的優勢。

圖6 3種算法的Hypervolume值

4 結束語

提出進化多目標合作博弈算法，解決CBSN中數據量、通信帶寬和傳感器節點能耗相互沖突問題。采用共謀合作博弈能夠在保證快速收斂的同時，實現目標的整體收益的最大化；采用Levy飛行和精英保留策略，擴大種群搜索范圍，實現全局收斂。仿真研究表明，該算法與現有算法相比較，其解集不僅具有更好的分布性與多樣性，而且收斂速度快，能夠有效實現體域網通信中數據量、通信帶寬和傳感器節點能耗三者之間的均衡。

[1]Movassaghi S,Abolhasan M,Lipman J,et al.Wireless body area networks:A survey[J].IEEE Communications Surveys & Tutorials,2014,16(3):1658-1686.

[2]Ghamari M,Janko B,Sherratt RS,et al.A survey on wireless body area networks for ehealthcare systems in residential environments[J].Sensors,2016,16(6):234-251.

[3]Fortino G,Fatta GD,Pathan M,et al.Cloud-assisted body area networks:State-of-the-art and future challenges[J].Wireless Networks,2014,20(7):1925-1938.

[4]Fortino G,Pathan M,Fortino G,et al.Integration of cloud computing and body sensor networks[C]//IEEE,International Conference on Cloud Computing Technology and Science.IEEE Computer Society,2012:57-61.

[5]Ren YC,Suzuki J,Omura S,et al.Evolutionarily reconfigurable cloud-integrated body sensor networks[C]//Internatio-nal Conference on E-Health Networking,Application & Ser-vices.IEEE,2015:78-102.

[6]Azzouz R,Bechikh S,Said LB.Dynamic multi-objective optimization using evolutionary algorithms:A survey[M]//Recent Advances in Evolutionary Multi-objective Optimization.Springer International Publishing,2017.

[7]ZHOU Hui,YANG Zhen,ZHU Liqing,et al.On the global convergence of real-coaded chemical reaction optimization[J].Systems Engineering Theory and Practice,2015,35(12):3233-3240(in Chinese).[周暉,楊振,朱立慶,等.實數編碼化學反應優化的全局收斂性研究[J].系統工程理論與實踐,2015,35(12):3233-3240.]

[8]Phan DH,Suzuki J,Omura S,et al.Toward sensor-cloud integration as a service:Optimizing three-tier communication in cloud-integrated sensor networks[C]//Int’l Conference on Body Area Networks.Boston:ACM,2013:212-219.

[9]Phan DH,Suzuki J,Omura S,et al.Multiobjective communication optimization for cloud-integrated body sensor networks[C]//IEEE/ACM International Symposium on Cluster,Cloud and Grid Computing.IEEE,2014:685-693.

[10]Xu M,Yang Q,Kwak K.Distributed topology control with lifetime extension based on non-cooperative game for wireless sensor networks[J].IEEE Sensors Journal,2016,16(9):3332-3342.

[11]Ren YC,Suzuki J,Phan DH,et al.An evolutionary game theoretic approach for configuring cloud-integrated body sensor networks[C]//IEEE International Symposium on Network Computing and Applications.Cambridge:IEEE,2014:277-281.

[12]Verdejo H,Gonzalez D,Delpiano J,et al.Tuning of power system stabilizers using multiobjective optimization NSGA-II[J].IEEE Latin America Transactions,2015,13(8):2653-2660.

[13]Suresh S,Lal S.An efficient cuckoo search algorithm based multilevel thresholding for segmentation of satellite images using different objective functions[J].Expert Systems with Applications,2016,58(C):184-209.

[14]LIU Jian,LI Jinghang,BAI Xiaoli.Reactive power optimization of distribution network using genetic algorithm with elitist strategy[J].Electrical Engineering,2015,16(4):35-38(in Chinese).[劉健,李京航,柏小麗.基于精英保留策略遺傳算法的配電網無功優化[J].電氣技術,2015,16(4):35-38.]

[15]Jiang S,Zhang J,Ong YS,et al.A simple and fast hypervolume indicator-based multiobjective evolutionary algorithm[J].IEEE Transactions on Cybernetics,2015,45(10):2202-2213.