孔 梅，朱曉娟

(安徽理工大學計算機科學與工程學院，安徽 淮南 232001)

0 引 言

無線傳感器網絡可以完成數據采集、處理和傳輸的任務，但是能量約束對整個WSN網絡系統(tǒng)的壽命造成了巨大的挑戰(zhàn)，限制了無線傳感器網絡的應用。目前拓撲控制的解決方案主要分三類：功率控制[1-2]、睡眠調度[3]和分簇[4]。博弈論中參與者競爭的過程能夠較好地描述節(jié)點之間節(jié)省能耗的競爭現象，因此被作為無線傳感器網絡中拓撲控制的重要工具。蔡釗[5]等人通過降低反向鏈路集中節(jié)點的發(fā)射功率，來調整自身的發(fā)射功率，從而延長潛在壽命。何亞光[6]等人根據節(jié)點剩余能量和節(jié)點到基站的距離來建立博弈模型,均衡了節(jié)點的能量消耗。王慧嬌[7]等人根據節(jié)點的平均壽命來調整節(jié)點功率。上述方法只能根據部分信息博弈，不能從整體進行優(yōu)化博弈。軟件定義網絡(Software-defined networking,SDN)為當前分布式網絡提供了新的發(fā)展機遇[8-9]。Deze Zeng[10]等人設計一種基于軟件定義的節(jié)能節(jié)點調度和管理策略，實現了全局的能耗優(yōu)化。王克重[11]等人為傳感器節(jié)點尋找中繼節(jié)點，降低距離基站較遠的節(jié)點能耗。但是其中繼節(jié)點的選擇沒有考慮剩余能量。Li Peizhe[12]等人在改進的SDWSN中提出一種基于非合作博弈的節(jié)能算法。但是對于能量達到閾值的節(jié)點，沒有介紹如何進行調整。針對傳統(tǒng)拓撲控制策略的不足，基于軟件定義無線傳感器網絡架構，提出一種非合作式博弈拓撲控制方法。在軟件定義的架構下，控制器具有全局視圖，能夠將博弈過程從節(jié)點轉移到控制器，從整體上根據網絡連通性和節(jié)點的剩余能量等進行博弈，來降低節(jié)點發(fā)射功率，節(jié)省能耗。

1 系統(tǒng)模型

1.1 網絡模型

現有的軟件定義網絡架構分為應用層、控制層和數據層，研究人員將SDN架構模型引入到無線傳感器當中來[13]，形成SDWSN架構模型。沿用這一思想，設計了如下圖所示的網絡架構。這里我們假設sink節(jié)點的能量不受限制，并具有較大的內存資源和計算能力，由sink節(jié)點擔任軟件定義架構中的控制器。

應用層作為交互層面，為用戶提供各種需要的服務?？刂茖臃譃閿祿邮铡⑼負浞治?、流表規(guī)則生成、控制信息四個模塊。傳感器節(jié)點收集到的信息首先傳送到數據接收模塊，然后數據接收模塊將數據整理后傳送到拓撲分析模塊。流表規(guī)則生成模塊根據拓撲分析模塊提供的信息生成規(guī)則，最后由控制信息模塊將生成規(guī)則傳遞給傳感器節(jié)點?；A設施層由多個普通傳感器節(jié)點組成，它們根據控制器下發(fā)的指令進行數據的收集和轉發(fā)。

圖1 SDWSN架構模型

架構中的控制器具有全局視圖，包括網絡拓撲、網絡可達性、網絡服務能力和服務質量等信息。網絡視圖可以用具有實體屬性的有向圖來表示。為了使控制器能夠更好地對網絡信息進行管理，應該給傳遞的網絡視圖消息規(guī)定特定格式的統(tǒng)一標簽，具體如表1所示。

表1 網絡視圖消息標簽

為了便于分析，我們做出如下假設：

1)在初始狀態(tài)下，節(jié)點用最大傳輸功率通信時，網絡是連通的，并且節(jié)點已經把感知區(qū)域全部覆蓋。

2)對于網絡中的所有傳感器節(jié)點，假設它們具有相同的最大發(fā)射功率和相同的初始能量。

將采用的符號整理如表2。

表2 符號集

從拓撲控制的角度而言，無線傳感器網絡可以抽象為一個有向圖G=。其中N={i=1,2,…,n}表示網絡中節(jié)點的集合，假設有n個節(jié)點隨機部署在監(jiān)測區(qū)域內；V是一個n×n矩陣，表示集合N中兩傳感器節(jié)點之間是否存在通信鏈路，P是節(jié)點發(fā)射功率的集合。

1.2 博弈論相關概念

一個策略非合作博弈可以用三元組表示為Γ=[14]。其中，V={V1,V2,…,Vn}是參與者集合，n是參與者數量；S=S1×S2×…×Sn是策略集Si的笛卡爾積，任意參與者Vi∈V,其策略集記為Si;Ui是第i個參與者的效用函數值。每個參與者自身的策略選擇記為si∈Si，其它參與者的策略選擇記為s-i。

定義1 納什均衡：如果一個參與者的當前策略能夠使自己的期望收益達到最大，并且其他參與者也滿足這樣的條件，那么這個策略組合被成為納什均衡。

(1)

定義2 序數勢博弈和序數勢函數：對于博弈Γ=，如果存在一個函數Y:S→R,?i∈V,?S-i∈S-i,?a,b∈Si,，滿足式(2)：

Ui(a,s-i)-Ui(b,s-i)>0

(2)

當且僅當如式(3)

Y(a,s-i)-Y(b,s-i)>0

(3)

那么稱博弈Γ為序數勢博弈，函數Y為序數勢函數。

定理1 如果策略博弈Γ=為序數勢博弈，且對應的函數Y為序數勢函數，則能夠使Y最大化的策略組合S就是博弈Γ的一個納什均衡。

2 基于非合作博弈的拓撲控制算法

2.1 效用函數

每個節(jié)點在拓撲構建過程中都要考慮到網絡連通性、傳輸功率、鏈路跳數及節(jié)點剩余能量，設定式(4)效用函數來計算每個節(jié)點的收益：

Ui(pi(t),p-i(t))

=ci(pi(t),p-i(t))fb(i)-fr(hi)

(4)

其中，pi(t)是節(jié)點i的功率，p-i(t)是除節(jié)點i之外其他節(jié)點的功率。ci(pi(t),p-i(t))的函數值為1或0，取值為1時說明當前節(jié)點i與控制器是連通的，取值為0說明兩者不連通。fb(i)是收益函數，具體表示為式(5)：

(5)

Er(i)是節(jié)點i的剩余能量，pi是節(jié)點i的當前發(fā)射功率。為了使自己收益更大，節(jié)點應該盡量在當前剩余能量下減小自己的發(fā)射功率。fr(hi)是阻礙函數，將它定義為關于鏈路跳數hi的單調遞增函數，跳數越大阻礙越大，效用函數值越小。

2.2 網絡連通性的判斷

在每輪博弈之后，控制器都會對當前網絡連通性進行判斷，從而決定ci的取值。規(guī)定了網絡連通的判斷準則：如果所有節(jié)點都能和控制器連通，那么網絡連通。從某個節(jié)點出發(fā)，用廣度優(yōu)先搜索的方法，判斷該節(jié)點是否與控制器連通。具體步驟如下：

Step 1：從節(jié)點vi開始，將其鄰居節(jié)點放入隊列q中；

Step 2：訪問隊首節(jié)點，如果該節(jié)點不是控制器，則彈出隊首節(jié)點并標記為已訪問，將其未訪問過的鄰居節(jié)點入隊；

Step 3：重復步驟2，直到訪問到控制器或隊列為空時停止；

Step 4：若迭代停止時未能訪問到控制器，說明該點不能和控制器連通；

Step 5：對余下的n-1個節(jié)點，重復上述步驟。

2.3 算法流程

1)初始化階段

各節(jié)點將自身信息，包括當前發(fā)射功率、鄰居節(jié)點集、剩余能量等，發(fā)送給控制器，控制器收到各節(jié)點的信息后，用節(jié)點的當前功率生成初始策略集，建立初始網絡拓撲結構。

2)博弈階段

按照節(jié)點序號，從最靠近控制器的節(jié)點依次開始博弈。開始時，節(jié)點剩余能量充足，可以選擇較小的功率作為自己的策略集。越靠近控制器的節(jié)點傳輸任務量越大，越需要降低傳輸功率來保存自身能量。所以從最靠近控制器的節(jié)點開始博弈，可以有效均衡各節(jié)點的剩余能量。在SDWSN架構下，控制器具有全局視圖，每輪博弈結束后，直接在數據存儲模塊更新策略集。在得到所有節(jié)點的策略后，控制器將策略集下發(fā)到網絡中。

對于節(jié)點來說，博弈過程就是尋找效用函數最大值的過程。從初始的最大傳輸功率開始，功率逐漸遞減，如果降低功率能夠獲得比當前發(fā)射功率下更大的效用函數值，則用更小功率替換當前功率；否則，停止迭代，把當前功率作為策略選擇，控制器更新策略集，進行下一個節(jié)點的博弈。

3)拓撲維護階段

為網絡節(jié)點設置能量閾值，當有節(jié)點能量達到閾值時，在全局拓撲視圖中刪掉該節(jié)點和相關鏈路，在新的全局拓撲視圖中重新開始博弈。

2.4 算法特性分析

定理2 如果各節(jié)點以最大傳輸功率pmax構建的網絡拓撲Gmax能夠連通，那么所提算法構建出的網絡拓撲G′也能保證網絡連通。

證明假設節(jié)點i達到納什均衡時的傳輸功率為pi′則pi′≤pmax,根據納什均衡的定義如式(6):

(6)

開始以最大傳輸功率通信時，網絡是連通的，ci(pmax,p-i)=1,如式(7)：

Ui(pmax,p-i)=fb(i)-fr(hi)

(7)

采用反證法，設傳輸功率為pi′時網絡不連通，則ci(pi′,p-i)=0，如式(8)：

(8)

將式(7)和(8)代入(6)得式(9)：

-fb(i)≥0

(9)

定理3 所提博弈模型是序數勢博弈，將對應的序數勢函數定義為式(10)：

Y(pi,p-i)=

(10)

證明假設piqi為節(jié)點的可選發(fā)射功率,當節(jié)點選擇這兩種不同的發(fā)射功率時，效用函數的差值為

Δui=ui(pi,p-i)-ui(qi,p-i)=

ci(pi(t),p-i(t))fb(i)-fr(hi)-

[ci(qi(t),p-i(t))fb(i)-fr(hi)]=

fr(hi)[ci(qi(t),p-i(t))-

ci(pi(t),p-i(t))]

類似的，

ΔY=Y(pi,p-i)-Y(qi,p-i)=

n(ci(qi(t),p-i(t))-

結果可以分為以下四種情況：

1)ci(pi(t),p-i(t))=ci(qi(t),p-i(t))=0

此時Δu=ΔY=0，同號；

2)ci(pi(t),p-i(t))=1,ci(qi(t),p-i(t))=0

顯然，Δui和ΔY同號；

3)ci(pi(t),p-i(t))=0,ci(qi(t),p-i(t))=1

與(2)同理可得，Δui和ΔY同號；

4)ci(pi(t),p-i(t))=ci(qi(t),p-i(t))=1

顯然，Δui和ΔY同號。

綜上所述，不論何種情況，Δui和ΔY始終同號，根據定義2，所提博弈模型為序數勢博弈，函數Y(pi,p-i)為序數勢函數。

推論1 所提博弈模型一定存在納什均衡。

證明根據定理1，使序數勢函數最大化的策略組合就是納什均衡解。序數勢函數是效用函數的累加和，博弈過程就是求每個節(jié)點最大效用函數值的過程，所以一定存在一個使序數勢函數最大化的策略組合，即博弈模型一定存在納什均衡。

3 仿真與結果分析

為了評價所提算法的性能，進行了仿真測試，實驗參數如下表所示。將傳感器節(jié)點隨機分布在300m×300m的正方形區(qū)域中，節(jié)點數量設置為50-300，控制器位于正方形區(qū)域的中間位置。

表3 仿真參數設置

將所提算法與其他博弈論算法對比，包括傳統(tǒng)架構下基于勢博弈的非均勻拓撲控制算法BLTC[6]，和SDWSN架構下的OPGEA算法[12]。部署不同數量的傳感器節(jié)點，測試三種算法在不同節(jié)點數量下的節(jié)點平均發(fā)射功率、鏈路平均跳數、網絡生存時間，以及不同時間下的節(jié)點剩余能量標準差。

圖2 三種算法的平均發(fā)射功率變化情況

圖3中，算法的平均跳數大于BLTC算法，小于OPGEA算法，這也與圖2相對應，節(jié)點發(fā)射功率小，則通信半徑也會變小，傳遞數據時通信鏈路的跳數就會增加。OPGEA算法與所提算法有相近的發(fā)射功率，但算法的鏈路跳數明顯小于OPGEA算法，說明算法在節(jié)點發(fā)射功率和鏈路跳數方面取得了較好的平衡。

圖3 三種算法的平均鏈路跳數變化情況

圖4 三種算法的網絡生存時間變化情況

圖5 三種算法的剩余能量變化情況

實驗將網絡生存時間定義為網絡中第一個節(jié)點死亡時間。圖4中，算法的生存時間遠大于BLTC算法，一方面得益于SDWSN架構的轉控分離，普通傳感器節(jié)點的復雜計算任務轉移到控制器，減少了能量消耗；另一方面是由于SDWSN架構下的博弈算法能夠更好地實現負載均衡，避免出現某一節(jié)點過早死亡的現象。

開始時，算法的剩余能量標準差略高于OPGEA算法，是由于在博弈過程中是根據節(jié)點距離控制器的遠近來確定博弈順序，最早進行博弈的節(jié)點，即離控制器最近的節(jié)點可以選擇盡可能小的發(fā)射功率；后進行博弈的節(jié)點為了保持網絡連通，就必須要適當增加自己的發(fā)射功率，所以一開始距離遠的節(jié)點能量消耗較快。

4 結 語

應用了軟件定義的思想，改進了SDWSN架構。SDWSN中轉控分離的特性將大大降低傳感器節(jié)點的計算要求，基于SDWSN，提出了一種非合作博弈節(jié)能算法。算法考慮了傳感器節(jié)點的剩余能量、傳輸功率以及網絡的連通性，使各個節(jié)點作為參與者進行博弈。與傳統(tǒng)架構下的博弈算法不同的是，SDWSN架構中的控制器對整個網絡具有全局視圖，能夠在控制器中對各個節(jié)點執(zhí)行博弈過程，提高了工作效率。實驗結果表明，算法能夠有效降低發(fā)射功率，平衡各節(jié)點間的能耗，延長網絡生命周期。