基于非完全信息博弈競(jìng)標(biāo)的無(wú)線傳感器網(wǎng)絡(luò)資源分配方法

張順華， 劉漳輝, 2

(1. 福州大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院， 福建 福州　350116; 2. 福建省網(wǎng)絡(luò)計(jì)算與智能信息處理重點(diǎn)實(shí)驗(yàn)室， 福建 福州　350116)

?

基于非完全信息博弈競(jìng)標(biāo)的無(wú)線傳感器網(wǎng)絡(luò)資源分配方法

張順華1， 劉漳輝1, 2

(1. 福州大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院， 福建 福州350116; 2. 福建省網(wǎng)絡(luò)計(jì)算與智能信息處理重點(diǎn)實(shí)驗(yàn)室， 福建 福州350116)

針對(duì)無(wú)線傳感器網(wǎng)絡(luò)任務(wù)調(diào)度過(guò)程中造成的資源沖突問(wèn)題， 將其考慮為節(jié)點(diǎn)間的非完全信息博弈競(jìng)標(biāo)過(guò)程； 在參與競(jìng)標(biāo)的節(jié)點(diǎn)進(jìn)行決策時(shí)， 引入隱馬爾可夫鏈預(yù)測(cè)其他競(jìng)爭(zhēng)者的決策， 將資源分配過(guò)程中的多個(gè)優(yōu)化目標(biāo)， 分別由任務(wù)和節(jié)點(diǎn)進(jìn)行優(yōu)化， 并提出一種非完全信息博弈競(jìng)標(biāo)算法； 在假設(shè)節(jié)點(diǎn)個(gè)人理性的前提條件下， 論證此非完全信息博弈競(jìng)標(biāo)模型滿足經(jīng)濟(jì)學(xué)原理中的激勵(lì)相容性和最大化系統(tǒng)收益. 最后并從實(shí)驗(yàn)仿真證明其有效性.

無(wú)線傳感器網(wǎng)絡(luò)； 資源分配； 競(jìng)標(biāo)； 博弈

0　引言

考慮到傳感器節(jié)點(diǎn)的異構(gòu)性和動(dòng)態(tài)性， 近幾年越來(lái)越多的學(xué)者研究結(jié)合經(jīng)濟(jì)學(xué)原理進(jìn)行資源分配， 如分配過(guò)程中引入效益函數(shù)， 在自適應(yīng)分配方法中將節(jié)點(diǎn)與任務(wù)虛擬成虛擬市場(chǎng)中的買家和賣家等等， 并取得了較好的成果. 如文獻(xiàn)[1-4]提出一種基于市場(chǎng)機(jī)制的資源分配算法， 該算法實(shí)現(xiàn)自主分配無(wú)線傳感器網(wǎng)絡(luò)中的稀有資源， 以實(shí)現(xiàn)能量均衡和最大化網(wǎng)絡(luò)生命周期. 文獻(xiàn)[5-8]提出一種基于組合拍賣機(jī)制的無(wú)線傳感器網(wǎng)絡(luò)任務(wù)調(diào)度算法， 通過(guò)市場(chǎng)機(jī)制調(diào)節(jié)資源間的合作以提高網(wǎng)絡(luò)的生命周期， 能有效實(shí)現(xiàn)傳感器資源的動(dòng)態(tài)分配. 文獻(xiàn)[9-10]提出新的基于組合雙向拍賣的資源分配模型. 前面文獻(xiàn)中提出的市場(chǎng)模型和組合拍賣模型在競(jìng)標(biāo)過(guò)程中只考慮到節(jié)點(diǎn)與任務(wù)之間的關(guān)系， 而忽略了節(jié)點(diǎn)與競(jìng)爭(zhēng)節(jié)點(diǎn)間的關(guān)系， 缺乏對(duì)整體信息的利用， 如應(yīng)用于現(xiàn)實(shí)場(chǎng)景， 很難做出最優(yōu)決策. 文獻(xiàn)[11]將博弈理論應(yīng)用到資源分配中， 并論證資源分配博弈中Nash均衡點(diǎn)的存在性和唯一性以及Nash均衡解. 文獻(xiàn)[12]將正比例資源共享的網(wǎng)格環(huán)境中多用戶競(jìng)爭(zhēng)同一計(jì)算資源問(wèn)題形式化為一個(gè)多人序貫博弈， 在節(jié)點(diǎn)的決策過(guò)程中， 將前輪博弈結(jié)果作為下次博弈的預(yù)測(cè)， 相當(dāng)于對(duì)整體信息的利用. 文獻(xiàn)[13]針對(duì)網(wǎng)格計(jì)算環(huán)境動(dòng)態(tài)、 異構(gòu)和分布的特性以及網(wǎng)格資源分配中資源利用率低、 效益不均等問(wèn)題， 結(jié)合微觀經(jīng)濟(jì)學(xué)理論， 把資源分配看作一場(chǎng)非完全信息博弈過(guò)程， 在實(shí)驗(yàn)部分證明比文獻(xiàn)[12]更優(yōu).

考慮到無(wú)線傳感器網(wǎng)絡(luò)與網(wǎng)格特征的相似性、 同為異構(gòu)性、 動(dòng)態(tài)性， 借鑒文獻(xiàn)[13]中的模型， 提出一種非完全信息博弈競(jìng)標(biāo)模型(non-complete information game bidding model, NCIGBM)應(yīng)用于無(wú)線傳感器網(wǎng)絡(luò)資源分配. 針對(duì)無(wú)線傳感器網(wǎng)絡(luò)資源的特征， 構(gòu)造相應(yīng)的效用函數(shù)， 并在以節(jié)點(diǎn)個(gè)人理性的前提條件下， 從理論上論證了此模型滿足經(jīng)濟(jì)學(xué)原理中的激勵(lì)相容性和最大化整體收益， 最后也從實(shí)驗(yàn)仿真部分驗(yàn)證其有效性.

1　資源分配問(wèn)題描述

假設(shè)一個(gè)無(wú)線傳感器網(wǎng)絡(luò)由m個(gè)傳感器組成， 有n個(gè)獨(dú)立任務(wù)要競(jìng)爭(zhēng)使用傳感器， 則資源管理的目標(biāo)就是合理地把傳感器資源分配給n個(gè)任務(wù)， 使任務(wù)的總完成時(shí)間最小， 傳感器上所消耗的能量最小， 傳感器能量均衡率最大. 任務(wù)在各傳感器上的執(zhí)行時(shí)間可以根據(jù)任務(wù)類型通過(guò)預(yù)測(cè)技術(shù)和實(shí)際歷史處理來(lái)預(yù)測(cè)估計(jì)， 具體的估計(jì)執(zhí)行時(shí)間可以用一個(gè)n×m的矩陣consume來(lái)表示， 其中的元素consumeij表示任務(wù)i在傳感器j上的估計(jì)執(zhí)行時(shí)間. 傳感器Sj的執(zhí)行時(shí)間為分配到該傳感器上的所有任務(wù)執(zhí)行時(shí)間之和， 具體表示如下：

(1)

由于各節(jié)點(diǎn)是并行工作， 因此所有任務(wù)的完成時(shí)間為節(jié)點(diǎn)中最大執(zhí)行時(shí)間， 具體表示如下：

(2)

無(wú)線傳感器網(wǎng)絡(luò)完成時(shí)間描述了任務(wù)被分配到最佳或近佳傳感器的程度， 它的值越小， 表示有越多的任務(wù)被分配到比較理想的傳感器上運(yùn)行， 可表示為：

(3)

此外， 傳感器在處理任務(wù)中能量消耗可表示為：

(4)

pcost為節(jié)點(diǎn)的單位時(shí)間所需能耗， 則傳感器的總能量消耗可表示為：

(5)

一個(gè)好的分配調(diào)度算法除了要保證傳感器網(wǎng)絡(luò)的總完成時(shí)間盡量短和所消耗的總能量盡可能少的同時(shí)， 還要保證傳感器網(wǎng)絡(luò)的能量平衡. 能量均衡率越高， 網(wǎng)絡(luò)的生命周期越長(zhǎng)， 能量均衡率可表示為：

(6)

式中: GAPmax=max{UEi}-min{UEi}， gapj=max{UEj}-UEj

綜上， 傳感器資源管理是一個(gè)多目標(biāo)優(yōu)化問(wèn)題， 其數(shù)學(xué)模型表示為：

maxLP

minUT,TE

式中: UT， TE， LP如公式(2)、 (5)、 (6)定義， 如果任務(wù)i分配給j則xij=1， 否則xij=0.

2　非完全信息博弈競(jìng)標(biāo)模型

2.1NCIGBM的結(jié)構(gòu)

在無(wú)線傳感器網(wǎng)絡(luò)中， 任務(wù)是實(shí)時(shí)的、 動(dòng)態(tài)的， 這是一個(gè)不確定的過(guò)程， 而每當(dāng)有任務(wù)到來(lái)， 會(huì)有很多節(jié)點(diǎn)同時(shí)滿足任務(wù)的要求， 會(huì)造成資源間的沖突. 應(yīng)用經(jīng)濟(jì)學(xué)原理的觀點(diǎn)， 這其實(shí)是一個(gè)博弈競(jìng)標(biāo)的過(guò)程. 各節(jié)點(diǎn)為博弈的參與者， 節(jié)點(diǎn)根據(jù)自身的狀態(tài)、 自身與任務(wù)的關(guān)系以及對(duì)競(jìng)爭(zhēng)節(jié)點(diǎn)決策的預(yù)測(cè)， 做出最優(yōu)決策; 在所有競(jìng)標(biāo)者都提交競(jìng)標(biāo)價(jià)后， 任務(wù)再根據(jù)自身的收益函數(shù)選擇最優(yōu)節(jié)點(diǎn)， 并將任務(wù)分配給競(jìng)標(biāo)勝節(jié)點(diǎn). NCIGBM結(jié)構(gòu)主要由三部分組成： 任務(wù)管理模塊、 競(jìng)標(biāo)管理模塊和節(jié)點(diǎn)管理模塊， 如圖1所示.

2.2非完全信息博弈競(jìng)標(biāo)機(jī)制

由上節(jié)可知， 無(wú)線傳感網(wǎng)絡(luò)資源分配為一多目標(biāo)優(yōu)化問(wèn)題， 其優(yōu)化目標(biāo)為任務(wù)的總執(zhí)行時(shí)間、 節(jié)點(diǎn)總消耗能量和各節(jié)點(diǎn)能量均衡率. 文中主要考慮任務(wù)Agent和節(jié)點(diǎn)Agent， 其中目標(biāo)任務(wù)的總執(zhí)行時(shí)間交由任務(wù)Agent優(yōu)化， 節(jié)點(diǎn)總消耗能量和節(jié)點(diǎn)能量均衡率作為節(jié)點(diǎn)Agent的優(yōu)化目標(biāo). 非完全信息博弈競(jìng)標(biāo)機(jī)制主要包括發(fā)標(biāo)、 競(jìng)標(biāo)、 評(píng)標(biāo)和中標(biāo)四個(gè)過(guò)程， 圖2為非完全信息博弈競(jìng)標(biāo)機(jī)制流程圖.

1) 發(fā)標(biāo)和競(jìng)標(biāo). 當(dāng)任務(wù)到來(lái)時(shí)， 任務(wù)會(huì)將其需求提交至發(fā)標(biāo)模塊， 然后發(fā)標(biāo)模塊將此需求封裝成消息廣播至各節(jié)點(diǎn). 而此時(shí)網(wǎng)絡(luò)中會(huì)有很多傳感器節(jié)點(diǎn)同時(shí)滿足需求， 這時(shí)就會(huì)產(chǎn)生一個(gè)資源沖突問(wèn)題， 如將傳感器節(jié)點(diǎn)看成智能個(gè)體， 則沖突問(wèn)題可以看成是競(jìng)爭(zhēng)問(wèn)題. 又因?yàn)閭鞲衅鞴?jié)點(diǎn)間信息了解的不全面性， 所以將節(jié)點(diǎn)間的競(jìng)標(biāo)考慮為非完全信息博弈過(guò)程， 節(jié)點(diǎn)為博弈的參與者， 其主要問(wèn)題是如何做出最優(yōu)決策以使自身的收益最大. 這里節(jié)點(diǎn)的決策以競(jìng)標(biāo)價(jià)的形式給出， 結(jié)合博弈理論及現(xiàn)實(shí)生活中競(jìng)標(biāo)過(guò)程， 競(jìng)標(biāo)者在做決策時(shí)會(huì)考慮自身與任務(wù)之間的關(guān)系， 自身與競(jìng)爭(zhēng)者之間的關(guān)系， 而自身與任務(wù)之間的關(guān)系為已知條件. 所以, 主要是如何精確估計(jì)競(jìng)爭(zhēng)者的決策， 以確定自身與競(jìng)爭(zhēng)者之間的關(guān)系. 在此, 本文引入隱馬爾可夫模型預(yù)測(cè)競(jìng)爭(zhēng)者的決策.

當(dāng)節(jié)點(diǎn)接收到發(fā)標(biāo)模塊廣播的招標(biāo)消息時(shí)， 節(jié)點(diǎn)會(huì)檢查自身狀態(tài)是否滿足任務(wù)需求， 如不滿足， 則不參與競(jìng)標(biāo); 如滿足， 則首先對(duì)任務(wù)需求生成價(jià)值估計(jì)， 用Vij表示， 此值也體現(xiàn)節(jié)點(diǎn)的偏好. 再結(jié)合其自身狀態(tài)、 競(jìng)爭(zhēng)者歷史競(jìng)標(biāo)信息和全局信息， 使用隱馬爾可夫模型預(yù)測(cè)此輪其他競(jìng)爭(zhēng)者的策略， 然后得出本輪競(jìng)標(biāo)勝的概率， 用Pij表示. 假設(shè)將競(jìng)標(biāo)者的最優(yōu)決策用GVij表示， 則競(jìng)標(biāo)者的收益可表示為:

隱馬爾可夫模型(HMM)包括隱含狀態(tài)集(S)、 可觀測(cè)狀態(tài)集(O)、 初始狀態(tài)概率矩陣(π) 、 隱含狀態(tài)轉(zhuǎn)移概率矩陣(A)和觀測(cè)狀態(tài)轉(zhuǎn)移概率矩陣(B)五個(gè)元素.

競(jìng)標(biāo)初期， 為每個(gè)節(jié)點(diǎn)生成一條隱馬爾可夫鏈， 其中各任務(wù)在各個(gè)節(jié)點(diǎn)上執(zhí)行所需要的能量為共同知識(shí)， 以各個(gè)任務(wù)在節(jié)點(diǎn)i上執(zhí)行所需能量作為節(jié)點(diǎn)i的HMM中的可觀測(cè)狀態(tài)Y， 以競(jìng)標(biāo)者的單位出價(jià)為隱含狀態(tài)， 其中A, B元素隨機(jī)分布于區(qū)間(0, 1)， 并保證∑πi=1， ∑jAij=1和∑jBij=1.

利用Baum-Welch算法訓(xùn)練出最優(yōu)參數(shù){π， A, B}通過(guò)Viterbi算法求出對(duì)于每個(gè)可觀測(cè)狀態(tài)對(duì)應(yīng)的最大概率的隱含狀態(tài). 在每輪競(jìng)標(biāo)過(guò)程中， 競(jìng)標(biāo)者利用全局信息和歷史信息， 再通過(guò)隱馬爾可夫鏈對(duì)競(jìng)爭(zhēng)者的單位出價(jià)進(jìn)行預(yù)測(cè)， 然后推算出本輪勝標(biāo)的概率， 可表示為：

式中： PB數(shù)組為節(jié)點(diǎn)對(duì)任務(wù)的單位競(jìng)標(biāo)價(jià).

假設(shè)各競(jìng)標(biāo)節(jié)點(diǎn)都為理性節(jié)點(diǎn)， 即以最大化自身利益為目標(biāo)， 競(jìng)標(biāo)者為了達(dá)到最高收益， 計(jì)算E’=0, 最后可求得

(7)

式中:A=Rij×W,Rij為任務(wù)i在節(jié)點(diǎn)j上執(zhí)行所需時(shí)間，W為其他競(jìng)爭(zhēng)者預(yù)測(cè)競(jìng)標(biāo)單價(jià)之和;V代表的是競(jìng)標(biāo)者與任務(wù)之間的關(guān)系， 也體現(xiàn)了競(jìng)標(biāo)者自身的狀態(tài)；A代表競(jìng)標(biāo)者與其他競(jìng)標(biāo)之間的關(guān)系， 即競(jìng)標(biāo)者與競(jìng)標(biāo)者之間的關(guān)系， 也就是個(gè)體與整體的關(guān)系.

競(jìng)標(biāo)者節(jié)點(diǎn)對(duì)任務(wù)的真實(shí)估價(jià)Vij， 可表示為：

(8)

2) 評(píng)標(biāo)和中標(biāo). 在每輪競(jìng)標(biāo)結(jié)束后， 競(jìng)標(biāo)模塊會(huì)將接收到的競(jìng)標(biāo)price集合傳給評(píng)標(biāo)模塊， 而評(píng)標(biāo)模塊會(huì)根據(jù)任務(wù)的偏好和提交的競(jìng)標(biāo)價(jià)擇出最優(yōu)競(jìng)標(biāo)者. 對(duì)于任務(wù)而言， 偏好于執(zhí)行時(shí)間短和可靠性高， 這里的可靠性理解為節(jié)點(diǎn)剩余能量多. 從節(jié)點(diǎn)的效用函數(shù)可以看出， 節(jié)點(diǎn)的剩余能量越多， 競(jìng)價(jià)越高. 因此可將任務(wù)的偏好， 即效用函數(shù)表示為:

(9)

式中:Tij為任務(wù)i在節(jié)點(diǎn)j上預(yù)計(jì)的執(zhí)行時(shí)間， 然后評(píng)標(biāo)模塊計(jì)算任務(wù)對(duì)各競(jìng)標(biāo)節(jié)點(diǎn)的偏好值， 并按從大到小排序， 并選出最大值作為本輪的競(jìng)標(biāo)勝者. 最后把競(jìng)標(biāo)勝者傳送給中標(biāo)模塊， 中標(biāo)模塊再將此消息傳給相應(yīng)的任務(wù)和廣播給各節(jié)點(diǎn)， 節(jié)點(diǎn)接收到廣播消息后, 如消息中的競(jìng)標(biāo)勝者為自身， 則將任務(wù)列入自己的待執(zhí)行任務(wù)列表， 并調(diào)整狀態(tài)； 如不是， 則不作任何變化.

2.3NCIGBM的主要算法

非完全信息博弈競(jìng)標(biāo)模型中主要算法步驟如下：

輸入： 任務(wù)對(duì)傳感器節(jié)點(diǎn)的需求矩陣consume數(shù)組, 節(jié)點(diǎn)單位時(shí)間所需能耗pcost數(shù)組, 節(jié)點(diǎn)對(duì)任務(wù)的競(jìng)標(biāo)價(jià)price數(shù)組, 權(quán)值系數(shù)a，b，c，d.

輸出： 任務(wù)的分配結(jié)果result數(shù)組.

步驟1初始化consume， pcost， price，a，b，c，d， result;

步驟2訓(xùn)練每個(gè)節(jié)點(diǎn)i的隱馬爾可夫鏈;

步驟2.1通過(guò)HMM算法為節(jié)點(diǎn)i生成一條隱馬爾可夫鏈;

步驟2.2通過(guò)Baum-Welch算法為節(jié)點(diǎn)i訓(xùn)練處最優(yōu)參數(shù){π，A,B};

步驟2.3通過(guò)Viterbi算法求出對(duì)于每個(gè)可觀測(cè)狀態(tài)對(duì)應(yīng)的最大概率的隱含狀態(tài);

步驟3計(jì)算任務(wù)i的最優(yōu)節(jié)點(diǎn)， 對(duì)于每個(gè)節(jié)點(diǎn)j;

步驟3.1判斷節(jié)點(diǎn)j是否能滿足任務(wù)i的需求， 如不滿足則跳到步驟3， 如滿足則轉(zhuǎn)到3.2;

步驟3.2計(jì)算各競(jìng)爭(zhēng)者的最大可能競(jìng)標(biāo)單價(jià)之和W;

步驟3.3根據(jù)公式(8)求出Vij， 根據(jù)公式(7)求出GVij;

步驟3.4根據(jù)Vij和GVij+求出競(jìng)標(biāo)價(jià)priceij;

步驟4將本輪各參與者提交的競(jìng)標(biāo)價(jià)傳給評(píng)標(biāo)模塊;

步驟5對(duì)每個(gè)節(jié)點(diǎn)根據(jù)公式(9)計(jì)算Eij;

步驟6選出最大Eij為競(jìng)標(biāo)勝節(jié)點(diǎn)， 將此消息通知給任務(wù)并廣播給各節(jié)點(diǎn)， 調(diào)整競(jìng)標(biāo)勝節(jié)點(diǎn)狀態(tài).

4　性能分析

NCIGBM是無(wú)線傳感器網(wǎng)絡(luò)中以經(jīng)濟(jì)學(xué)理論為依托的模型， 本節(jié)將從激勵(lì)相容和系統(tǒng)收益兩個(gè)方面分析證明其效用.

2)最大化系統(tǒng)收益. 在無(wú)線傳感器網(wǎng)絡(luò)中， 系統(tǒng)收益為任務(wù)收益和節(jié)點(diǎn)收益之和， 假設(shè)系統(tǒng)總收益用E表示， 任務(wù)收益用TE表示， 節(jié)點(diǎn)收益用NE表示， 則E可表示為：

因?yàn)樵诟?jìng)標(biāo)過(guò)程中， 節(jié)點(diǎn)總是最大化自身收益， 因此priceij為節(jié)點(diǎn)的最優(yōu)值， 而在評(píng)標(biāo)階段， 任務(wù)是選取log(priceij/consumeij)值最大的作為勝標(biāo)節(jié)點(diǎn)， 因此也為最優(yōu)值. 綜上， 在節(jié)點(diǎn)和任務(wù)都最大化自身收益的同時(shí)， 系統(tǒng)收益也最大化.

5　實(shí)驗(yàn)仿真

模擬實(shí)驗(yàn)選取GREED、 IPSO算法[14]和SMM算法[15]進(jìn)行橫向比較, 比較的主要性能指標(biāo)有總執(zhí)行時(shí)間、 總消耗能量和節(jié)點(diǎn)的能量均衡率.

5.1參數(shù)設(shè)置

由于現(xiàn)實(shí)生活中無(wú)線傳感器網(wǎng)絡(luò)大多為異構(gòu)網(wǎng)絡(luò)， 為了滿足異構(gòu)性， 本文將參數(shù)設(shè)置如下： 傳感器節(jié)點(diǎn)隨機(jī)分布在100 m×100 m的環(huán)境中， 任務(wù)對(duì)各資源節(jié)點(diǎn)的需求consume隨機(jī)分布于[1 s, 10 s]， 值越大表示任務(wù)在此傳感器節(jié)點(diǎn)上執(zhí)行所需的時(shí)間越長(zhǎng)， 節(jié)點(diǎn)的單位時(shí)間所需能耗隨機(jī)分布于(0 MJ/s, 1 MJ/s]， 值越大表示節(jié)點(diǎn)執(zhí)行單位時(shí)間需消耗的能量越多， 節(jié)點(diǎn)的初始能量值隨機(jī)分布于[30 MJ, 50 MJ]， 對(duì)于節(jié)點(diǎn)效用函數(shù)參數(shù)β設(shè)為20，α設(shè)為0.9. 節(jié)點(diǎn)數(shù)和任務(wù)數(shù)值的設(shè)定分為5種情況： 節(jié)點(diǎn)數(shù)遠(yuǎn)少于任務(wù)數(shù)、 節(jié)點(diǎn)數(shù)略少于任務(wù)數(shù)、 節(jié)點(diǎn)數(shù)等于任務(wù)數(shù)、 節(jié)點(diǎn)數(shù)略大于任務(wù)數(shù)和節(jié)點(diǎn)數(shù)遠(yuǎn)大于任務(wù)數(shù).

5.2實(shí)驗(yàn)分析

分別選取以能耗為貪心原則的GREED、 IPSO和SMM進(jìn)行對(duì)比， 實(shí)驗(yàn)結(jié)果如表1和圖3所示.

表1　GREED、 SMM、 IPSO和NCIGBA總消耗能量Tab.1　The total energy consumption of GREED、 SMM、 IPSO and NCIGBA

從表1可以看出， 隨著節(jié)點(diǎn)數(shù)的增加， GREED算法得出的總消耗能量逐漸增加， 而SMM、 IPSO和NCIGBA得出的總消耗能量總體呈下降趨勢(shì)， 因?yàn)殡S著節(jié)點(diǎn)數(shù)的增多， 任務(wù)的可選節(jié)點(diǎn)增多， 故能得到更優(yōu)的分配. 對(duì)比SMM、 IPSO和NCIGBA的總消耗能量， 當(dāng)節(jié)點(diǎn)數(shù)遠(yuǎn)小于任務(wù)數(shù)時(shí)， IPSO得出的總消耗能量低于SMM得出的總消耗能量; 隨著節(jié)點(diǎn)數(shù)的增多， IPSO得到的總消耗能量逐漸與SMM得到的總消耗能量相同， 8組數(shù)據(jù)中， NCIGBA得出總消耗能量一直低于GREED、 SMM和IPSO得出的總消耗能量.

從圖3(a)中可以看出， 總執(zhí)行時(shí)間性能指標(biāo)隨著節(jié)點(diǎn)數(shù)的增加， NCIGBA、 IPSO和SMM得到的總執(zhí)行時(shí)間慢慢減少， 并逐漸趨于穩(wěn)定， 而GREED得到的總執(zhí)行時(shí)間變化較大， 并遠(yuǎn)遠(yuǎn)大于NCIGBA、 IPSO和SMM得到的. 在節(jié)點(diǎn)數(shù)較少的時(shí)候， SMM得到的總執(zhí)行時(shí)間略大于IPSO， 都大于NCIGBA， 隨著節(jié)點(diǎn)數(shù)的增加， NCIGBA、 IPSO、 SMM得到的總執(zhí)行時(shí)間基本相同， 趨于最優(yōu).

從圖3(b)中可以看出， NCIGBA得到的能量均衡率值最大， IPSO和GREED次之， SMM最小， 由前面的分析結(jié)果可以看出GREED的總執(zhí)行時(shí)間和總消耗能量遠(yuǎn)遠(yuǎn)大于NCIGBA、 IPSO和SMM. 因此， 結(jié)合總執(zhí)行時(shí)間、 總消耗能量和能量均衡率3個(gè)性能指標(biāo)， GREED最差， IPSO優(yōu)于SMM， NCIGBA最優(yōu).

為了進(jìn)一步驗(yàn)證本文方法的有效性， 對(duì)SMM、 IPSO、 NCIGBA進(jìn)行更大規(guī)模的實(shí)驗(yàn)仿真， 任務(wù)數(shù)和節(jié)點(diǎn)數(shù)(n，m)的值分別取(50， 10)、 (50， 25)、 (50， 50)、 (50， 75)和(50， 100)， 分別對(duì)應(yīng)任務(wù)數(shù)和節(jié)點(diǎn)數(shù)值之間關(guān)系的5種類型， 每種類型隨機(jī)生成100組不同的數(shù)據(jù)進(jìn)行實(shí)驗(yàn)， 然后得出各算法的總執(zhí)行時(shí)間平均值(AT)、 總消耗能量平均值(AE)和能量均衡率平均值(ALP)， 實(shí)驗(yàn)結(jié)果如表2所示.

表2　SMM、 IPSO和NCIGBA實(shí)驗(yàn)結(jié)果Tab.2　The experimental results of SMM、 IPSO and NCIGBA

從表2可以看出， 隨著節(jié)點(diǎn)數(shù)的增加， SMM、 IPSO和NCIGBA得到的平均總執(zhí)行時(shí)間、 平均總消耗能量和平均能量均衡率值呈減少趨勢(shì)， 并且下降的幅度慢慢減少. 對(duì)于任務(wù)數(shù)和節(jié)點(diǎn)數(shù)之間值大小的五種不同類型， IPSO總體優(yōu)于SMM， 而NCIGBA的各項(xiàng)性能指標(biāo)均優(yōu)于IPSO和SMM.

6　結(jié)語(yǔ)

針對(duì)無(wú)線傳感器網(wǎng)絡(luò)任務(wù)調(diào)度過(guò)程中造成的資源沖突問(wèn)題， 本文將其視為節(jié)點(diǎn)間的非完全信息博弈競(jìng)標(biāo)過(guò)程， 并提出一種非完全博弈競(jìng)標(biāo)算法進(jìn)行資源分配， 此算法以一種自主的觀點(diǎn)進(jìn)行資源分配， 具有自適應(yīng)特性， 同時(shí)也能很好滿足于網(wǎng)絡(luò)的動(dòng)態(tài)性和異構(gòu)性. 最后在實(shí)驗(yàn)仿真部分證明了NCIGBA得到的總執(zhí)行時(shí)間、 總消耗能量和能量均衡率三個(gè)優(yōu)化性能指標(biāo)均優(yōu)于GREED、 SMM和IPSO.

[1] ZIMMERMAN A T, LYNCH J P, FERRESE F T. Market-based resource allocation for distributed data processing in wireless sensor networks[J]. ACM Transactions on Embedded Computing Systems,2013, 12(3): 84:1-28.DOI:10.1145/2442116.2442134.

[2] SCHRAGE D, FARNHAM C, GONSALVES P G. A market-based optimization approach to sensor and resource management[C]//Intelligent Computing: Theory and Applications IV.Priddy:SPIE, 2006.DOI:10.1117/12.665153.

[3] LEE D H, HAN J H, KIM J H. Market-based multiagent framework for balanced task allocation[M]//Robot Intelligence Technology and Applications 2012. Berlin:Springer, 2013: 549-559.DOI:10.1007/978-3-642-37374-9_53.

[4] EDALAT N, XIAO W, THAM C K,etal. A price-based adaptive task allocation for wireless sensor network[C]// 2009 IEEE 6th International Conference on Mobile Adhoc and Sensor Systems. Macau: IEEE, 2009: 888-893. DOI:10.1109/MOBHOC.2009.5337039.

[5] KHAN M I, RINNER B, REGAZZONI C S. Resource coordination in wireless sensor networks by combinatorial auction based method[C]// 2012 IEEE 3rd International Conference on Networked Embedded Systems for Every Application. Liverpool:IEEE, 2012: 1-6. DOI:10.1109/NESEA.2012.6474012.

[6] VISWANATH A, MULLEN T, HALL D,etal. MASM: a market architecture for sensor management in distributed sensor networks[C]// Multisensor, Multisource Information Fusion: Architectures, Algorithms, and Applications 2005. Florida: SPIE, 2005: 281-289.DOI:10.1117/12.604074.

[7] BANGLA A K, CASTANON D. Asynchronous auction for distributed nonlinear resource allocation[C]// 2011 50th IEEE Conference on Decision and Control and European Control Conference. Orlando: IEEE, 2011: 4 467-4 472.DOI:10.1109/CDC.2011.6161247.

[8] LI Y, GAO Z, YANG Y,etal. An improved auction scheme for task allocation in wireless sensor network[C]// 2010 6th International Conference on Wireless Communications Networking and Mobile Computing. Chengdu: IEEE, 2010: 1-4.DOI:10.1109/WICOM.2010.5601143.

[9] 翁楚良, 陸鑫達(dá). 一種基于雙向拍賣機(jī)制的計(jì)算網(wǎng)格資源分配方法[J]. 計(jì)算機(jī)學(xué)報(bào), 2006, 29(6): 1 004-1 009.

[10] 李立, 劉元安, 馬曉雷. 基于組合雙向拍賣的網(wǎng)格資源分配[J]. 電子學(xué)報(bào), 2009, 37(1): 165-169.

[11] 陶軍, 吳清亮, 吳強(qiáng). 基于非合作競(jìng)價(jià)博弈的網(wǎng)絡(luò)資源分配算法的應(yīng)用研究[J]. 電子學(xué)報(bào), 2006, 34(2): 241-246.

[12] 李志潔, 程春田, 黃飛雪, 等. 一種基于序貫博弈的網(wǎng)格資源分配策略[J]. 軟件學(xué)報(bào), 2006, 17(11): 2 373-2 383.

[13] 李明楚, 許雷, 孫偉峰, 等. 基于非完全信息博弈的網(wǎng)格資源分配模型[J]. 軟件學(xué)報(bào), 2012, 23(2): 428-438.

[14] XIA T, GUO W, CHEN G. An improved particle swarm optimization for data streams scheduling on heterogeneous cluster[M]//Advances in Computation and Intelligence. Berlin: Springer, 2007: 393-400.DOI:10.1007/978-3-540-74581-5_43.

[15] WU M Y, SHU W, ZHANG H. Segmented min-min: a static mapping algorithm for meta-tasks on heterogeneous computing systems[C]//Heterogeneous Computing Workshop. Cancun: IEEE, 2000.DOI:http://doi.ieeecomputersociety.org/10.1109/HCW.2000.843759.

(責(zé)任編輯： 蔣培玉)

A non-complete information game bidding method for resource allocation in wireless sensor networks

ZHANG Shunhua1, LIU Zhanghui1, 2

(1. College of Mathematics and Computer Science, Fuzhou University, Fuzhou, Fujian 350116, China;2. Fujian Provincial Key Laboratory of Network Computing and Intelligent Information Processing, Fuzhou, Fujian 350116, China)

For the resource conflicts issue caused during task scheduling in wireless sensor networks, we consider it as the non-complete information game bidding process between the nodes. When the joined nodes make decisions, we introduce the hidden Markov chains to predict the decisions of other competitors. Meanwhile, we assign the optimization objectives of resource allocation problem to the task agents and node agents, and propose a non-complete information game bidding algorithm. Finally, under the assumption of joined node individual rationality, we demonstrate that this non-complete information game bidding model meet the principles of incentive compatibility and maximize system revenue. And its validity be proved from simulation experiments.

wireless sensor networks; resource allocation; bidding; game

10.7631/issn.1000-2243.2016.01.0045

1000-2243(2016)01-0045-07

2014-03-11

劉漳輝(1971-)， 副教授， 主要從事智能網(wǎng)絡(luò)技術(shù)研究， lzh@fzu.edu.cn

國(guó)家自然科學(xué)基金項(xiàng)目(61103175); 教育部科學(xué)技術(shù)研究重點(diǎn)項(xiàng)目(212086); 福建省科技創(chuàng)新平臺(tái)項(xiàng)目(2009J1007); 福建省高校杰出青年人才計(jì)劃項(xiàng)目(JA12016); 福建省高校新世紀(jì)人才計(jì)劃項(xiàng)目(JA13021)

TP393

A