SDWSN中基于非合作博弈的拓?fù)淇刂扑惴á?/h1>

2021-12-21 03:17:56朱曉娟

佳木斯大學(xué)學(xué)報(bào)(自然科學(xué)版)訂閱 2021年6期 收藏

關(guān)鍵詞：序數(shù)發(fā)射功率架構(gòu)

孔 梅，朱曉娟

(安徽理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，安徽 淮南 232001)

0 引 言

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

1 系統(tǒng)模型

1.1 網(wǎng)絡(luò)模型

現(xiàn)有的軟件定義網(wǎng)絡(luò)架構(gòu)分為應(yīng)用層、控制層和數(shù)據(jù)層，研究人員將SDN架構(gòu)模型引入到無(wú)線傳感器當(dāng)中來(lái)[13]，形成SDWSN架構(gòu)模型。沿用這一思想，設(shè)計(jì)了如下圖所示的網(wǎng)絡(luò)架構(gòu)。這里我們假設(shè)sink節(jié)點(diǎn)的能量不受限制，并具有較大的內(nèi)存資源和計(jì)算能力，由sink節(jié)點(diǎn)擔(dān)任軟件定義架構(gòu)中的控制器。

應(yīng)用層作為交互層面，為用戶提供各種需要的服務(wù)?？刂茖臃譃閿?shù)據(jù)接收、拓?fù)浞治?、流表?guī)則生成、控制信息四個(gè)模塊。傳感器節(jié)點(diǎn)收集到的信息首先傳送到數(shù)據(jù)接收模塊，然后數(shù)據(jù)接收模塊將數(shù)據(jù)整理后傳送到拓?fù)浞治瞿K。流表規(guī)則生成模塊根據(jù)拓?fù)浞治瞿K提供的信息生成規(guī)則，最后由控制信息模塊將生成規(guī)則傳遞給傳感器節(jié)點(diǎn)?；A(chǔ)設(shè)施層由多個(gè)普通傳感器節(jié)點(diǎn)組成，它們根據(jù)控制器下發(fā)的指令進(jìn)行數(shù)據(jù)的收集和轉(zhuǎn)發(fā)。

圖1 SDWSN架構(gòu)模型

架構(gòu)中的控制器具有全局視圖，包括網(wǎng)絡(luò)拓?fù)洹⒕W(wǎng)絡(luò)可達(dá)性、網(wǎng)絡(luò)服務(wù)能力和服務(wù)質(zhì)量等信息。網(wǎng)絡(luò)視圖可以用具有實(shí)體屬性的有向圖來(lái)表示。為了使控制器能夠更好地對(duì)網(wǎng)絡(luò)信息進(jìn)行管理，應(yīng)該給傳遞的網(wǎng)絡(luò)視圖消息規(guī)定特定格式的統(tǒng)一標(biāo)簽，具體如表1所示。

表1 網(wǎng)絡(luò)視圖消息標(biāo)簽

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

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

2)對(duì)于網(wǎng)絡(luò)中的所有傳感器節(jié)點(diǎn)，假設(shè)它們具有相同的最大發(fā)射功率和相同的初始能量。

將采用的符號(hào)整理如表2。

表2 符號(hào)集

從拓?fù)淇刂频慕嵌榷?，無(wú)線傳感器網(wǎng)絡(luò)可以抽象為一個(gè)有向圖G=。其中N={i=1,2,…,n}表示網(wǎng)絡(luò)中節(jié)點(diǎn)的集合，假設(shè)有n個(gè)節(jié)點(diǎn)隨機(jī)部署在監(jiān)測(cè)區(qū)域內(nèi)；V是一個(gè)n×n矩陣，表示集合N中兩傳感器節(jié)點(diǎn)之間是否存在通信鏈路，P是節(jié)點(diǎn)發(fā)射功率的集合。

1.2 博弈論相關(guān)概念

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

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

(1)

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

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

(2)

當(dāng)且僅當(dāng)如式(3)

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

(3)

那么稱博弈Γ為序數(shù)勢(shì)博弈，函數(shù)Y為序數(shù)勢(shì)函數(shù)。

定理1 如果策略博弈Γ=為序數(shù)勢(shì)博弈，且對(duì)應(yīng)的函數(shù)Y為序數(shù)勢(shì)函數(shù)，則能夠使Y最大化的策略組合S就是博弈Γ的一個(gè)納什均衡。

2 基于非合作博弈的拓?fù)淇刂扑惴?/h2>

2.1 效用函數(shù)

每個(gè)節(jié)點(diǎn)在拓?fù)錁?gòu)建過(guò)程中都要考慮到網(wǎng)絡(luò)連通性、傳輸功率、鏈路跳數(shù)及節(jié)點(diǎn)剩余能量，設(shè)定式(4)效用函數(shù)來(lái)計(jì)算每個(gè)節(jié)點(diǎn)的收益：

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

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

(4)

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

(5)

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

2.2 網(wǎng)絡(luò)連通性的判斷

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

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

Step 2：訪問(wèn)隊(duì)首節(jié)點(diǎn)，如果該節(jié)點(diǎn)不是控制器，則彈出隊(duì)首節(jié)點(diǎn)并標(biāo)記為已訪問(wèn)，將其未訪問(wèn)過(guò)的鄰居節(jié)點(diǎn)入隊(duì)；

Step 3：重復(fù)步驟2，直到訪問(wèn)到控制器或隊(duì)列為空時(shí)停止；

Step 4：若迭代停止時(shí)未能訪問(wèn)到控制器，說(shuō)明該點(diǎn)不能和控制器連通；

Step 5：對(duì)余下的n-1個(gè)節(jié)點(diǎn)，重復(fù)上述步驟。

2.3 算法流程

1)初始化階段

各節(jié)點(diǎn)將自身信息，包括當(dāng)前發(fā)射功率、鄰居節(jié)點(diǎn)集、剩余能量等，發(fā)送給控制器，控制器收到各節(jié)點(diǎn)的信息后，用節(jié)點(diǎn)的當(dāng)前功率生成初始策略集，建立初始網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。

2)博弈階段

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

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

3)拓?fù)渚S護(hù)階段

為網(wǎng)絡(luò)節(jié)點(diǎn)設(shè)置能量閾值，當(dāng)有節(jié)點(diǎn)能量達(dá)到閾值時(shí)，在全局拓?fù)湟晥D中刪掉該節(jié)點(diǎn)和相關(guān)鏈路，在新的全局拓?fù)湟晥D中重新開始博弈。

2.4 算法特性分析

定理2 如果各節(jié)點(diǎn)以最大傳輸功率pmax構(gòu)建的網(wǎng)絡(luò)拓?fù)銰max能夠連通，那么所提算法構(gòu)建出的網(wǎng)絡(luò)拓?fù)銰′也能保證網(wǎng)絡(luò)連通。

證明假設(shè)節(jié)點(diǎn)i達(dá)到納什均衡時(shí)的傳輸功率為pi′則pi′≤pmax,根據(jù)納什均衡的定義如式(6):

(6)

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

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

(7)

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

(8)

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

-fb(i)≥0

(9)

定理3 所提博弈模型是序數(shù)勢(shì)博弈，將對(duì)應(yīng)的序數(shù)勢(shì)函數(shù)定義為式(10)：

Y(pi,p-i)=

(10)

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

Δ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))-

結(jié)果可以分為以下四種情況：

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

此時(shí)Δu=ΔY=0，同號(hào)；

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

顯然，Δui和ΔY同號(hào)；

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

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

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

顯然，Δui和ΔY同號(hào)。

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

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

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

3 仿真與結(jié)果分析

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

表3 仿真參數(shù)設(shè)置

將所提算法與其他博弈論算法對(duì)比，包括傳統(tǒng)架構(gòu)下基于勢(shì)博弈的非均勻拓?fù)淇刂扑惴˙LTC[6]，和SDWSN架構(gòu)下的OPGEA算法[12]。部署不同數(shù)量的傳感器節(jié)點(diǎn)，測(cè)試三種算法在不同節(jié)點(diǎn)數(shù)量下的節(jié)點(diǎn)平均發(fā)射功率、鏈路平均跳數(shù)、網(wǎng)絡(luò)生存時(shí)間，以及不同時(shí)間下的節(jié)點(diǎn)剩余能量標(biāo)準(zhǔn)差。

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

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

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

圖4 三種算法的網(wǎng)絡(luò)生存時(shí)間變化情況

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

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

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

4 結(jié) 語(yǔ)

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

猜你喜歡

序數(shù)發(fā)射功率架構(gòu)

無(wú)線電波發(fā)射功率防爆要求與檢測(cè)方法

工礦自動(dòng)化(2024年6期)2024-08-22 00:00:00

基于FPGA的RNN硬件加速架構(gòu)

成都信息工程大學(xué)學(xué)報(bào)(2022年4期)2022-11-18 07:31:10

有序數(shù)方塊

數(shù)學(xué)小靈通(1-2年級(jí))(2021年12期)2021-12-30 06:28:16

功能架構(gòu)在電子電氣架構(gòu)開發(fā)中的應(yīng)用和實(shí)踐

汽車工程(2021年12期)2021-03-08 02:34:30

生活中的有序數(shù)對(duì)

中學(xué)生數(shù)理化·七年級(jí)數(shù)學(xué)人教版(2018年4期)2018-06-28 03:26:28

放大轉(zhuǎn)發(fā)中繼器降低發(fā)射功率的選擇策略研究

無(wú)線互聯(lián)科技(2017年24期)2018-01-22 10:39:24

淺談AC在WLAN系統(tǒng)中的應(yīng)用

中國(guó)管理信息化(2017年18期)2018-01-04 18:41:52

『基數(shù)』和『序數(shù)』

小學(xué)生學(xué)習(xí)指導(dǎo)(低年級(jí))(2017年9期)2017-08-07 02:12:34

LSN DCI EVPN VxLAN組網(wǎng)架構(gòu)研究及實(shí)現(xiàn)

電信科學(xué)(2017年6期)2017-07-01 15:45:17

基于功率分配最優(yōu)中繼選擇的研究

物聯(lián)網(wǎng)技術(shù)(2017年2期)2017-03-15 17:18:11

佳木斯大學(xué)學(xué)報(bào)(自然科學(xué)版)2021年6期

佳木斯大學(xué)學(xué)報(bào)(自然科學(xué)版)的其它文章

大數(shù)據(jù)環(huán)境中計(jì)算機(jī)網(wǎng)絡(luò)安全存儲(chǔ)研究①

車載移動(dòng)泵站液壓驅(qū)動(dòng)系統(tǒng)設(shè)計(jì)方法研究①

基于數(shù)據(jù)挖掘的工程項(xiàng)目動(dòng)態(tài)風(fēng)險(xiǎn)評(píng)估研究①

基于BM3D降噪算法在塔吊裂縫圖像中的應(yīng)用①

PROFIBUS非周期通訊技術(shù)在NT6000系統(tǒng)中的實(shí)現(xiàn)及應(yīng)用①

礦井勘探鉆孔多參量監(jiān)測(cè)系統(tǒng)設(shè)計(jì)①