張恒，郭超平

（1.陜西省商貿(mào)學(xué)校計(jì)算機(jī)教研室，陜西西安710065；2.西安通信學(xué)院陜西西安710106）

WMN（Wireless Mesh Networks）是一種給用戶提供更好服務(wù)的無(wú)線網(wǎng)絡(luò)，包含有兩種節(jié)點(diǎn)：路由器（Mesh Router）和客戶端（Mesh Client）。其中，路由器為客戶端的業(yè)務(wù)進(jìn)行路由轉(zhuǎn)發(fā)；客戶端除了要和其它客戶端通信之外，還要轉(zhuǎn)發(fā)其它客戶端的業(yè)務(wù)。然而，轉(zhuǎn)發(fā)其它客戶端的業(yè)務(wù)需要消耗資源，如帶寬和能量，付出一定的代價(jià)。因此，自私的客戶端不情愿轉(zhuǎn)發(fā)其它客戶端的業(yè)務(wù)。在路由協(xié)議方面，文獻(xiàn)[1-3]提出在WMN中使用修改的AODV路由協(xié)議，沒(méi)有考慮到客戶端的資源消耗情況。如何設(shè)計(jì)WMN的AODV路由協(xié)議，激勵(lì)自私客戶端參與業(yè)務(wù)轉(zhuǎn)發(fā)，實(shí)現(xiàn)WMN的帶寬與路由分配，仍是一個(gè)挑戰(zhàn)。

針對(duì)上述問(wèn)題，本文分析了WMN網(wǎng)絡(luò)中自私客戶端的理性行為，并將其建模為GSP拍賣(mài)模型，然后提出了基于GSP拍賣(mài)和粒子群優(yōu)化的AODV路由協(xié)議，最后進(jìn)行了總結(jié)。

1 相關(guān)工作

1.1 拍賣(mài)理論簡(jiǎn)述

拍賣(mài)機(jī)制（auction mechanism）是一組在非協(xié)作，競(jìng)爭(zhēng)環(huán)境下對(duì)稀缺資源的分配規(guī)則：拍賣(mài)方（auctioneer）根據(jù)競(jìng)爭(zhēng)者（bidder）對(duì)資源的出價(jià)（bid）決定他能獲取的資源份額以及相關(guān)的支付（payment）。Vickery拍賣(mài)（也叫第二價(jià)格拍賣(mài)，second price auction）和GSP（generalized second price）拍賣(mài)是其中的兩種。在Vickery拍賣(mài)中，勝利競(jìng)爭(zhēng)者而造成的其他競(jìng)爭(zhēng)者的代價(jià)差異決定了對(duì)他的支付。與Vickery拍賣(mài)相比，GSP拍賣(mài)只考慮僅次于考慮勝利競(jìng)爭(zhēng)者的下一個(gè)競(jìng)爭(zhēng)者的代價(jià)，它已被谷歌和雅虎用于因特網(wǎng)的廣告拍賣(mài)[4]中。文獻(xiàn)[2]指出Vickery拍賣(mài)能夠保證競(jìng)爭(zhēng)者的誠(chéng)實(shí)性（Truth-telling），而GSP拍賣(mài)不能保證節(jié)點(diǎn)的誠(chéng)實(shí)性。

拍賣(mài)已經(jīng)被廣泛地應(yīng)用到自私多跳網(wǎng)絡(luò)的路由：文獻(xiàn)[5]提出在自私網(wǎng)絡(luò)的路由時(shí)使用VCG拍賣(mài)進(jìn)行帶寬分配；文獻(xiàn)[6]提出使用Vickery拍賣(mài)與自私行為斗爭(zhēng)并促進(jìn)網(wǎng)絡(luò)間的合作；文獻(xiàn)[7]首先提出了基于VCG拍賣(mài)的路由協(xié)議并指出VCG拍賣(mài)存在的overpayment問(wèn)題，然后提出了基于第一價(jià)格拍賣(mài)的路由協(xié)議，其并沒(méi)有給出兩個(gè)參數(shù)和是如何取值的；文獻(xiàn)[8]提出使用GSP拍賣(mài)實(shí)現(xiàn)多徑多跳網(wǎng)絡(luò)的路由，并沒(méi)有給出保證節(jié)點(diǎn)誠(chéng)實(shí)性的分配比例的取值方法。

1.2 自私節(jié)點(diǎn)代價(jià)函數(shù)的定義

在定義節(jié)點(diǎn)代價(jià)函數(shù)的時(shí)候，考慮到WMN中節(jié)點(diǎn)對(duì)哪些資源的消耗更為關(guān)注。文獻(xiàn)[9]指出：路由器對(duì)于移動(dòng)性和功率有效性基本沒(méi)有限制，而客戶端支持一定的移動(dòng)性，需要支持功率有效性的路由協(xié)議。而客戶端參與轉(zhuǎn)發(fā)時(shí)最主要的是消耗自己的能量，這嚴(yán)重影響了它的壽命。為了激勵(lì)自私客戶端節(jié)點(diǎn)參與轉(zhuǎn)發(fā)，源客戶端支付給他一定的電子貨幣，每個(gè)客戶端可用賺取的電子貨幣支付給轉(zhuǎn)發(fā)自己業(yè)務(wù)的客戶端。客戶端主要任務(wù)是發(fā)送自己的業(yè)務(wù)，而不是賺取電子貨幣。在不同電子貨幣數(shù)量和能量時(shí)一個(gè)客戶端轉(zhuǎn)發(fā)其他客戶端的傾向性是不同的：

1）當(dāng)客戶端的電子貨幣較多而能量較少時(shí)，轉(zhuǎn)發(fā)其他客戶端業(yè)務(wù)的代價(jià)較高，它不是很愿意轉(zhuǎn)發(fā)其它客戶端的業(yè)務(wù)；當(dāng)客戶端的電子貨幣較多而能量較多時(shí)，轉(zhuǎn)發(fā)其它客戶端業(yè)務(wù)的代價(jià)較低，它非常愿意轉(zhuǎn)發(fā)其它客戶端的業(yè)務(wù)。

2）當(dāng)客戶端的電子貨幣較少而能量較少時(shí)，轉(zhuǎn)發(fā)其它客戶端業(yè)務(wù)的代價(jià)非常高，它很不愿意轉(zhuǎn)發(fā)其它客戶端的業(yè)務(wù)；當(dāng)客戶端的電子貨幣較少而能量較多時(shí)，轉(zhuǎn)發(fā)其它客戶端業(yè)務(wù)的代價(jià)較高，它不很愿意轉(zhuǎn)發(fā)其它客戶端的業(yè)務(wù)。

總之，能量的重要性遠(yuǎn)大于電子貨幣。借鑒文獻(xiàn)[6]的思想，代價(jià)函數(shù)的定義如下：

定義1當(dāng)一個(gè)客戶端vi在具有電子貨幣Ci和能量Ei的條件下，轉(zhuǎn)發(fā)其它很業(yè)務(wù)量q而付出的代價(jià)與當(dāng)前的能量Ei成反比，與當(dāng)前電子貨幣Ci的對(duì)數(shù)和業(yè)務(wù)量q成正比，即：

這里，η為常量，作為一個(gè)參數(shù)在電子貨幣和能量之間的平衡因子，為了實(shí)現(xiàn)能量消耗均勻取值為16。在某一時(shí)間段內(nèi)或某一時(shí)刻，可以認(rèn)

1.3 粒子群算法綜述

在粒子群算法[10]中，每個(gè)個(gè)體稱(chēng)為一個(gè)“粒子”，代表著一個(gè)潛在的解。例如，在一個(gè)H維的目標(biāo)搜索空間中，每個(gè)粒子看成是空間的一個(gè)點(diǎn)。設(shè)群內(nèi)由K個(gè)粒子構(gòu)成。K也被稱(chēng)為群體規(guī)模。設(shè)γk=（γk1，γk2，…，γkH）為第k個(gè)粒子（k=1，2，…，K）的H維位置矢量，根據(jù)事先設(shè)定的適應(yīng)值（與要解決的問(wèn)題有關(guān)）計(jì)算γk當(dāng)前的適應(yīng)值，即可衡量粒子的位置優(yōu)劣；λk=（λk1，λk2，…，λkH）為粒子的飛行速度，即粒子移動(dòng)的距離；ρk=（ρk1，ρk2，…，ρkH）為粒子迄今為止搜索到的最優(yōu)位置；ζk=（ζk1，ζk2，…，ζkH）為粒子迄今為止搜索到的最優(yōu)位置。

在每次迭代中，粒子根據(jù)以下式子更新速度和位置：

其中h=1，2，…，H，g是迭代次數(shù)，r1和r2為[0，1]之間的隨機(jī)數(shù)，c1和c2為學(xué)習(xí)因子，使粒子具有自我總結(jié)和向群體中優(yōu)秀個(gè)體學(xué)習(xí)的能力，從而向自己的歷史最優(yōu)點(diǎn)和群體最優(yōu)點(diǎn)靠近。粒子根據(jù)它上一次迭代的速度、當(dāng)前的位置和自身最好經(jīng)驗(yàn)與群體最好經(jīng)驗(yàn)之間的距離來(lái)更新速度；然后粒子根據(jù)式（3）飛向新的位置。為了改善粒子群的收斂性能，Shi和Eberhart引入慣性權(quán)式中[11]，即：

慣性權(quán)重起到權(quán)衡局部最優(yōu)和全局最優(yōu)能力的作用。其中，wmax為初始權(quán)重；wmin為最終權(quán)重，itermax為最大迭代次數(shù)。這樣，粒子群算法在剛開(kāi)始的時(shí)候傾向于開(kāi)掘，然后逐漸轉(zhuǎn)向開(kāi)拓，從而在局部區(qū)域調(diào)整解。

2 AODV路由協(xié)議

2.1 系統(tǒng)模型

假設(shè)WMN由有限個(gè)節(jié)點(diǎn)組成，表示為G=（V，E），其中V=（v1，v2，…，vn）是n個(gè)節(jié)點(diǎn)組成，節(jié)點(diǎn)有兩種類(lèi)型：路由器和客戶端；E=（e1，e2，…，el）是l條鏈路的集合。假設(shè)任意兩個(gè)客戶端或任意客戶端－路由器對(duì)是可達(dá)的（即它們之間至少存在一條通信路徑）。假設(shè)客戶端是自私，理性而非串謀的，期望自己在轉(zhuǎn)發(fā)其它客戶端的業(yè)務(wù)時(shí)付出的代價(jià)盡可能小。

AODV路由協(xié)議是一個(gè)用于移動(dòng)Ad hoc網(wǎng)絡(luò)的主動(dòng)式路由協(xié)議，并不能直接應(yīng)用到WMN中，需要稍微修改即可。當(dāng)源客戶端S和目的客戶端/路由器D（客戶端和路由器通信的目的是希望和Internet等通信）之間有一個(gè)帶寬為q的業(yè)務(wù)請(qǐng)求，它廣播路由請(qǐng)求分組RREQ（Route Request Packet）。每個(gè)收到RREQ的中間客戶端/路由器，如果收到的RREQ不是前面收到的RREQ的復(fù)制，在增加跳數(shù)之后廣播這個(gè)RREQ。當(dāng)目的客戶端/路由器D收到這個(gè)RREQ后，產(chǎn)生一個(gè)路由應(yīng)答分組RREP（Route Reply Packet）并按來(lái)時(shí)路由單播回去，一直到S。在返回RREP的過(guò)程中，中間客戶端vi將系數(shù)fi和可用帶寬bi加密后一起添加RREP中，而中間路由器ri添加自己的可用帶寬bi（其代價(jià)函數(shù)為0）。對(duì)于客戶端vi，代價(jià)函數(shù)fi和可用帶寬bi構(gòu)成了vi的類(lèi)型ti=＜fi，bi＞。假設(shè)經(jīng)過(guò)路由發(fā)現(xiàn)之后，S和D之間不相交的每條路徑包含客戶端的路徑集合為P={P1，P2，…，Pm}，不相交的每條路徑上節(jié)點(diǎn)全為包含路由器的路徑集合為P={P1，P2，…，Pd}。

S要給予中間客戶端一定的支付以激勵(lì)它們參與業(yè)務(wù)的轉(zhuǎn)發(fā)，并且這個(gè)支付要大于它付出的代價(jià)。在這個(gè)博弈中，每個(gè)vi選擇一個(gè)行動(dòng)ai，這個(gè)行動(dòng)是宣布它的當(dāng)前可用帶寬和代價(jià)函數(shù)。因此，參與人的行動(dòng)決定了代價(jià)函數(shù)fi（zi）和支付函數(shù)pi。因此，vi的效用函數(shù)是：

每個(gè)中間客戶端的目標(biāo)是最大化自己的效用函數(shù)，而源客戶端S的目標(biāo)是通過(guò)在這m條路徑之間合理地分配帶寬和路由使總的代價(jià)最小化。令P和P’中路徑Pj可用帶寬為Bj=min{bi|vi∈Pj∪ri∈Pj}，P’總的可用帶寬中路徑Pj的代價(jià)函數(shù)Pj的帶寬為zj。假設(shè)q＞BP′，需要P中路徑提供的帶寬為（q－BP′）。這樣的系統(tǒng)模型為拍賣(mài)模型，表示為：

2.1.1 給予中間mesh客戶端vMCi的支付

S要給予vi一定的支付以激勵(lì)它們參與業(yè)務(wù)的轉(zhuǎn)發(fā)。本文采用GSP拍賣(mài)，在S收到所有RREP以后，計(jì)算出P中每條路徑的代價(jià)并按照從小到大的順序進(jìn)行排序，集合P變?yōu)長(zhǎng)CP={PLCP1，PLCP2，…，PLCPm}（對(duì)于s≤t，那么Fs≤Ft）。如果客戶端vi位于PLCPj，那么給予客戶端vi的支付為：

2.1.2 附加約束條件

為了保證參與客戶端的誠(chéng)實(shí)性，參與帶寬分配的路徑數(shù)和每條路徑分配的帶寬必須滿足一定的條件[8]：

1）P中參與帶寬分配的路徑數(shù)小于P的路徑總數(shù)，假設(shè)有m個(gè)（m′＜m）路徑參與帶寬分配。

2）每條路徑分配的帶寬占P中所有參與帶寬分配的路徑的分配帶寬總和的比例滿足以下限制，對(duì)于任意s＜t，（Fs+1－

對(duì)上述不等式的兩邊同乘Fs）zt，從而系統(tǒng)模型變?yōu)镚SP拍賣(mài)模型，即：

式（14）是模型的誠(chéng)實(shí)性保證。顯然式（11）～（14）為一凸優(yōu)化問(wèn)題，直接用凸優(yōu)化的方法進(jìn)行求解可獲得帶寬和路由分配的結(jié)果，但是這樣會(huì)帶來(lái)大量的計(jì)算，尤其是（14）式。采用粒子群算法對(duì)上述的問(wèn)題求解進(jìn)行優(yōu)化，可快速找到最佳分配結(jié)果。

2.2 基于GSP拍賣(mài)和粒子群優(yōu)化的AODV路由分配算法

源客戶端S在收到所有RREP后，運(yùn)行基于GSP拍賣(mài)和粒子群優(yōu)化的AODV路由分配算法。利用粒子群優(yōu)化算法，可以快速找到滿足限制條件的最優(yōu)解，加快算法的收斂速度。

算法描述如下：源客戶端首先將從S到D的所有路徑分為兩個(gè)集合P和P′，計(jì)算P′中每條路徑的可用帶寬及其和BP′。然后S判斷P′中各條路徑的可用帶寬之和BP′是否大于等于q，如果是，算法結(jié)束，否則算法繼續(xù)。接著，計(jì)算P中每條路徑的代價(jià)函數(shù)和可用帶寬，并對(duì)P中每條路路徑按照路徑代價(jià)從小到大的順序進(jìn)行排序，得到最小代價(jià)路徑集合LCP。然后，選出LCP中的前面m′條路徑，可用帶寬之和大于等于（q－BP′）。最后，S利用粒子群優(yōu)化算法對(duì)式（11）～（12）求解；如果無(wú)解，將m′加1，重新求解，這樣一直到求得最優(yōu)解。算法的偽代碼如下：

算法1利用粒子算法求解的基于GSP拍賣(mài)的路由分配算法

輸入：P中每條路徑的所有節(jié)點(diǎn)的可用帶寬和代價(jià)函數(shù)，P′中每條路徑的所有節(jié)點(diǎn)的可用帶寬。

輸出：P和P′中每條路徑的分配的帶寬以及所有節(jié)點(diǎn)的的支付。

步驟2：計(jì)算P中路徑Pj的代價(jià)Fj，按照Fj從小到大的順序?qū)中的路徑排序，得到LCP；從LCP中選取前面m′條路徑，使其可用帶寬之和滿足不小于（q-BP′）。

步驟3：c1=c2=2；wmax=0.9，wmin=0.4，max_gen=100，初始化

步驟5：如m′加1，返回步驟4；否則輸出這m′條路徑以及步驟1中分配的結(jié)果。

3 結(jié)論

本文分析了自私WMN網(wǎng)絡(luò)中mesh客戶端的理性行為，并將其建模為GSP拍賣(mài)模型。然后提出了基于GSP拍賣(mài)和粒子群優(yōu)化的AODV路由協(xié)議。此算法收斂速度較快，可以直接在客戶端側(cè)實(shí)現(xiàn)，協(xié)議簡(jiǎn)單，可對(duì)AODV協(xié)議稍微修改就可應(yīng)用到WMN中去。

[1]KONG Peng-yong，WANG Hai-guang，GE Yu，et al.A performance comparision of routing protocols for maritime wireless mesh networks[C]//IEEE.WCNC 2008，2008:2170－2175.

[2]XIAN Xiao-dong，F(xiàn)U Yun-qing，WANG Song-jian，et al.A routing protocol based on combinative metric for wireless mesh networks[C]//IEEE.ICNS 2009，2009:803－806.

[3]Pirzada A A，Wishart R，Portmann M.Multi-linked AODV routing for wireless mesh networks[C]//IEEE.Globecom 2007，2007:4925－4930.

[4]Edelman B，Ostrovsky M，Schwarz M.Internet advertising and the generalized second price auction:selling billions of dollars worth of keywords，american economic review No.1917[R].Stanford：Stanford Graduate School of Business，2007.

[5]WU Fan，ZHONG Sheng，LIU Ji-qiang，et al.Cost-effective traffic assignment for multipath routing in selfsih networks[C]//IEEE.GLOBECOM 2007，2007:453－457.

[6]Demir C，Comaniciu C.An auction based AODV protocol for mobile ad hoc networks with selfish nodes[C]//IEEE.ICC 2007，2007:3351－3356.

[7]WANG Yu，WANG Weizhao，Dahlberg T A.Truthful routing for wireless hybrid networks[C]//IEEE.GLOBECOM 2005，2005:3461–3465.

[8]Xueyuan S，Chan S，Peng G.Auction in multi-path multihop routing[J].IEEE Communications Letters，2009，13（2）:154-156.

[9]Ian F.Akyildiz，Xudong W.A survey on wireless mesh networks[J].IEEE Communications Magazine，2005，43（9）:523-530.

[10]Kennedy J，Eberbart R C.Particle swarm optimization[C]//IEEE.Proceeding of IEEE International Conference on Neural Networks，1995:1942-1948.

[11]Shi Y，Eberbart R C.A modified particle swarm optimizer[C]//IEEE.Proceeding of IEEE International Conference on Evolutionary Computation，Anchorage.1998:69-73.