陳宇婷，劉廣鐘

(上海海事大學(xué) 信息工程學(xué)院,上海 201306)

0 引 言

無線傳感器網(wǎng)絡(luò)的分布性、獨立性、移動性等特點,使得網(wǎng)絡(luò)中的大部分功能要依靠節(jié)點間的相互協(xié)作來進(jìn)行。

目前通常假設(shè)所有網(wǎng)絡(luò)節(jié)點都具有良好的協(xié)作性,即每個節(jié)點都愿意為其他節(jié)點提供服務(wù)。但是這種假設(shè)在實際的無線傳感器網(wǎng)絡(luò)環(huán)境中并不一定成立，無線傳感器網(wǎng)絡(luò)節(jié)點由于受到自身處理能力、存儲空間、電池容量等各種資源的限制[1]，自私節(jié)點會不愿意幫助其他節(jié)點轉(zhuǎn)發(fā)信息,這會影響無線網(wǎng)絡(luò)正常的路由和數(shù)據(jù)轉(zhuǎn)發(fā)功能。如何激勵自私節(jié)點進(jìn)行合作,并且誠實地進(jìn)行合作以提高網(wǎng)絡(luò)性能,是當(dāng)前無線傳感器網(wǎng)絡(luò)研究領(lǐng)域面臨的重大挑戰(zhàn)之一,對于無線傳感器網(wǎng)絡(luò)的發(fā)展有著重要意義。

對于該問題，目前主要有基于信譽機制和基于支付機制。基于信譽機制，文獻(xiàn)[2]中提出了算法：檢測不良行為節(jié)點，同時，由Pathrater根據(jù)路徑中節(jié)點的平均信譽值選擇可靠的路由，避開不良節(jié)點。但該算法只是在路由選擇時避開不良節(jié)點，沒有對不良節(jié)點進(jìn)行限制或懲罰，不能做到激勵良好節(jié)點合作，未能充分利用節(jié)點，網(wǎng)絡(luò)的整體性能并沒有得到改善[2]。

基于支付機制的算法，通過支付虛擬貨幣補償節(jié)點轉(zhuǎn)發(fā)的能耗，激勵節(jié)點合作，例如文獻(xiàn)[3]。文獻(xiàn)[4]中的PFAG算法利用支付機制建立多階段博弈拍賣模型轉(zhuǎn)發(fā)路徑，與LEACH相比在降低和平衡網(wǎng)絡(luò)能耗方面效果較好，但在文中假設(shè)所有節(jié)點是完全信息博弈，在實際無線傳感器網(wǎng)絡(luò)中更多是不完全信息博弈。文中只討論部分文獻(xiàn)，其他有關(guān)節(jié)點合作參考文獻(xiàn)[5-10]。

1 問題建模

文中的網(wǎng)絡(luò)結(jié)構(gòu)模型如圖1所示。基站遠(yuǎn)離傳感器節(jié)點，簇頭節(jié)點負(fù)責(zé)控制簇內(nèi)節(jié)點的協(xié)同，簇內(nèi)的普通傳感器節(jié)點向相應(yīng)的簇頭發(fā)送數(shù)據(jù)，簇頭節(jié)點將收集到的數(shù)據(jù)信息進(jìn)行壓縮融合處理，之后發(fā)送到基站。

圖1 簇頭節(jié)點向基站發(fā)送數(shù)據(jù)

對于基于支付機制算法，都會有第三方收取稅收，文中由簇頭節(jié)點收取簇內(nèi)稅務(wù)，再由基站從簇頭收取稅務(wù)。

在無線傳感器網(wǎng)絡(luò)中，數(shù)據(jù)轉(zhuǎn)發(fā)需注意能耗均衡問題，易出現(xiàn)部分節(jié)點過分活躍，過早死亡，網(wǎng)絡(luò)分割?；谥Ц稒C制，文中引用付酬的多階段拍賣模型激勵節(jié)點轉(zhuǎn)發(fā)；同時考慮由于在拍賣過程中是不完全信息博弈，節(jié)點會出現(xiàn)過度虛假報價引起的整條路徑支付過高的情況。文中對競價中的節(jié)點報價和節(jié)點自私進(jìn)行討論，結(jié)合VCG思想做出合理標(biāo)價，使整條路徑支付和節(jié)點收益最優(yōu)；在報酬支付時，結(jié)合信譽激勵使用支付部分定金，轉(zhuǎn)發(fā)成功后支付報酬，激勵節(jié)點提高轉(zhuǎn)發(fā)成功率和誠信支付以保證路徑的可靠性，以此來找到一條最優(yōu)路徑。

2 算法模型

能耗模型為無線通信能量消耗模型，發(fā)送比特數(shù)據(jù)到距離為d的節(jié)點或基站的能量消耗[11]，即信號發(fā)射電路與信號放大電路的能耗之和：

(1)

其中，Eelec表示信號發(fā)射電路的能量損耗;εfs和εmp表示功率放大損耗;d0=87 m為距離閾值。發(fā)送節(jié)點與接收節(jié)點距離小于閾值則采用自由空間模型；否則采用多路衰減模型[12]。

2.1 路由發(fā)現(xiàn)模型

無線傳感器網(wǎng)絡(luò)中，自私節(jié)點不進(jìn)行自主的積極合作，拒絕作為中間節(jié)點為其他源節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)，假定節(jié)點間不存在共謀。

圖2中，當(dāng)節(jié)點A要將采集到的數(shù)據(jù)發(fā)送給目的節(jié)點時，A看作拍賣博弈的目的節(jié)點的代理買家，向周圍節(jié)點購買轉(zhuǎn)發(fā)服務(wù)，A廣播購買轉(zhuǎn)發(fā)服務(wù)的消息給周圍的鄰居節(jié)點，鄰居節(jié)點會為了獲得收益參與競拍，將其看作拍賣博弈賣方。按照此方法向下廣播，到達(dá)最接近簇首S的節(jié)點，簇頭回一個確認(rèn)消息給最接近自己的節(jié)點，確定連接可建立。

從最后端v8、v7和v6、v5、v4開始考慮競價，節(jié)點計算出各自的競拍真實價格，分布式計算，源節(jié)點不需要一直維護(hù)整個路徑，每層代理買家節(jié)點自行處理。

v6、v7、v8出價競爭，假設(shè)v7獲得轉(zhuǎn)發(fā)機會，v2記錄v7的價格，v2計算自己報價，然后將記錄的v7報價與自己報價發(fā)送給v0，v0只需處理v2和v3給出的報價，進(jìn)行競爭，直到A節(jié)點將競爭出整條路徑path，A節(jié)點將整條路徑價格記錄，同數(shù)據(jù)一起從路徑發(fā)送出去。

圖2 節(jié)點路由發(fā)現(xiàn)結(jié)構(gòu)

2.2 競拍模型

定義鄰居節(jié)點i的真實報價為：

(2)

其中，w為節(jié)點信譽值，每一個節(jié)點都有一個初始信譽值w，對于式2信譽值高的節(jié)點更容易競拍成功，增大信譽好的節(jié)點參與轉(zhuǎn)發(fā)的機會；γ=ak為源節(jié)點支付給下一節(jié)點的定金，a為固定常量值且是公共信息，k為數(shù)據(jù)比特值，由源節(jié)點廣播；d為到下個轉(zhuǎn)發(fā)節(jié)點的距離，每個競拍節(jié)點可根據(jù)賣方廣播時的時間戳與收到廣播的時間差計算得到，e'為剩余能量，eij為轉(zhuǎn)發(fā)數(shù)據(jù)所需能量，d、e'、eij都是節(jié)點的私人信息即根據(jù)其計算出的真實報價也為私人信息。當(dāng)e'-eij<0時即剩余能量不足以轉(zhuǎn)發(fā)時，報價會低于能耗和定金的和，自私節(jié)點不會參與到競價中，e'-eij=0時不成立則不參與報價。其他條件相同時，d越小則成功傳輸機率越高，能耗越低其報價越低，使易成功傳輸節(jié)點獲得轉(zhuǎn)發(fā)機會更高。

當(dāng)轉(zhuǎn)發(fā)能耗相同，剩余能量越高時，報價越低，使剩余能量較多的節(jié)點可以有更多的機會參加到轉(zhuǎn)發(fā)，更均衡地利用節(jié)點，以期降低和平衡網(wǎng)絡(luò)能耗。

2.3 VCG機制

(3)

(4)

一般在機制設(shè)計時，文獻(xiàn)[13-14]將效用函數(shù)ui考慮為擬線性：

ui=pi+ηi

(5)

在文中，pi為支付函數(shù)，ηi為真實報價轉(zhuǎn)發(fā)收益。

對于誠實機制，滿足：

(1)節(jié)點的策略為報告自己的私有類型θi=si；

定義一個整體最優(yōu)輸出結(jié)果o*(s)，為節(jié)點策略選擇后所得到的輸出結(jié)果o(s)中總體最優(yōu)。

根據(jù)上述定義，設(shè)計輸出函數(shù)及支付函數(shù)滿足：

(6)

此處定義支付函數(shù)為：

(7)

(8)

將公式進(jìn)行處理，可得ui：

2.4 基于VCG機制思想的節(jié)點標(biāo)價

對于虛假報價，做一個簡化結(jié)構(gòu)圖(見圖3)進(jìn)行討論。

圖3 節(jié)點路由選擇結(jié)構(gòu)簡化圖

(10)

下面進(jìn)行討論：

2.5 報酬支付

在貨幣機制中一般都默認(rèn)或明確提出第三方定期收取稅務(wù)，簇內(nèi)則由簇頭定期收取稅務(wù)，簇間基站為可信第三方。

源節(jié)點得到簇頭的確認(rèn)消息后開始發(fā)送數(shù)據(jù)，同時支付下一節(jié)點定金γ，收到定金則進(jìn)行轉(zhuǎn)發(fā)，否則不轉(zhuǎn)發(fā)，轉(zhuǎn)發(fā)成功才會拿到全部報酬，想獲得最大收益的理性自私節(jié)點不會為了定金而丟棄數(shù)據(jù)包不轉(zhuǎn)發(fā)。

這里的簇頭節(jié)點是簇內(nèi)其他條件相同時信譽值最高即付酬自私性最低的節(jié)點。

經(jīng)整理每個轉(zhuǎn)發(fā)節(jié)點收益為：

(11)

收到報酬的節(jié)點向下一節(jié)點發(fā)送ack傳遞報酬之后一次轉(zhuǎn)發(fā)完成，節(jié)點自行退出路徑，且考慮到節(jié)點的移動性和能耗，本次得到的路徑下次可能因為中間某個節(jié)點的能量耗盡或者離開而斷開，每個節(jié)點有數(shù)據(jù)轉(zhuǎn)發(fā)時就開始上述過程在現(xiàn)有環(huán)境中再開始一次競拍，這也使得能量多的節(jié)點有更多機會參與，能量少的節(jié)點避免過早死亡，整體范圍上增加了網(wǎng)絡(luò)節(jié)點存活量、延長了生命周期。

考慮到節(jié)點的自私性，在獲得目的節(jié)點或上一節(jié)點的報酬后發(fā)送ack卻少付或不付給下一節(jié)點，此時下一節(jié)點對其計數(shù)減1，并廣播計數(shù)情況,正常付給報酬則不廣播改變計數(shù)。

設(shè)置閾值W=1，當(dāng)對其計數(shù)w小于1時，節(jié)點將其定義為騙子節(jié)點，在一個較大時間內(nèi)將其排出網(wǎng)絡(luò)，拒絕為其轉(zhuǎn)發(fā)數(shù)據(jù)，使其無法收益，一定時間后將計數(shù)恢復(fù)到1。

3 仿真實驗

為了對算法進(jìn)行測試和分析，使用MATLAB進(jìn)行仿真實驗。實驗是由100個傳感器節(jié)點隨機分布在100 m×100 m的范圍內(nèi)。其中Eelec=50 nJ/bit，多徑衰減模型εmp=0.001 3 pJ/(bit×m4),εfs=10 pJ/(bit×m4)，每個節(jié)點的初始能量為2 J/node，w=5，節(jié)點接收單位數(shù)據(jù)的能耗和數(shù)據(jù)融合能耗為γ=5 nJ/bit。

圖4為一段時間內(nèi)是否使用VCG對總支付的影響，直接根據(jù)最低競拍節(jié)點報價標(biāo)價支付，則總支付高出使用VCG機制后的支付值，自私節(jié)點的虛高報價使路徑支付過高，容易導(dǎo)致預(yù)算超支問題。這表示基于VCG思想的標(biāo)價機制，能有效均衡網(wǎng)絡(luò)總支付，降低預(yù)算超支概率。

圖4 VCG機制下時間與總支付關(guān)系曲線

圖5是存活節(jié)點數(shù)量時間圖。部分算法中檢測不良節(jié)點并避開,只同合作節(jié)點進(jìn)行合作，使得部分節(jié)點過度消耗死亡，部分節(jié)點不能充分利用，剩余存活節(jié)點較少。文中算法激勵合作，同時考慮節(jié)點能量、距離等因素，在競拍時有效利用高剩余能量短發(fā)送距離節(jié)點，均衡網(wǎng)絡(luò)節(jié)點能耗，使得節(jié)點存活數(shù)量較多。

圖5 剩余節(jié)點數(shù)量時間

圖6為一段時間后節(jié)點收益圖，信譽都有變化，且信譽高的節(jié)點總收益明顯高于信譽低的節(jié)點。這是由于節(jié)點信譽變低后，稅收變高競拍成功幾率變低，參與轉(zhuǎn)發(fā)獲取報酬的機會減少，故此總收益會低于信譽高的節(jié)點，對于理性節(jié)點不支付下一節(jié)點報酬的行為會減少，促進(jìn)節(jié)點間良好協(xié)作，少部分信譽低節(jié)點收益高，是由于上一輪不傳遞報酬，但大部分節(jié)點信譽等級同收益成正比。

圖6 節(jié)點收益

4 結(jié)束語

提出了一種基于VCG的無線傳感器網(wǎng)絡(luò)路由算法，考慮能耗條件使用拍賣博弈激勵，有效促進(jìn)自私節(jié)點合作，結(jié)合支付機制與信譽機制提高了節(jié)點數(shù)據(jù)轉(zhuǎn)發(fā)量。在考慮節(jié)點自私情況下，結(jié)合VCG機制思想，控制節(jié)點過高虛假報價，有效均衡路徑總支付。但是文中考慮節(jié)點理性，無惡意攻擊篡改等，在以后的研究中會將非理性節(jié)點惡意攻擊這些情況進(jìn)行完善，并設(shè)計到算法中。