基于GSP拍賣和粒子群優化的AODV協議

張恒，郭超平

（1.陜西省商貿學校計算機教研室，陜西西安710065；2.西安通信學院陜西西安710106）

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

針對上述問題，本文分析了WMN網絡中自私客戶端的理性行為，并將其建模為GSP拍賣模型，然后提出了基于GSP拍賣和粒子群優化的AODV路由協議，最后進行了總結。

1 相關工作

1.1 拍賣理論簡述

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

拍賣已經被廣泛地應用到自私多跳網絡的路由：文獻[5]提出在自私網絡的路由時使用VCG拍賣進行帶寬分配；文獻[6]提出使用Vickery拍賣與自私行為斗爭并促進網絡間的合作；文獻[7]首先提出了基于VCG拍賣的路由協議并指出VCG拍賣存在的overpayment問題，然后提出了基于第一價格拍賣的路由協議，其并沒有給出兩個參數和是如何取值的；文獻[8]提出使用GSP拍賣實現多徑多跳網絡的路由，并沒有給出保證節點誠實性的分配比例的取值方法。

1.2 自私節點代價函數的定義

在定義節點代價函數的時候，考慮到WMN中節點對哪些資源的消耗更為關注。文獻[9]指出：路由器對于移動性和功率有效性基本沒有限制，而客戶端支持一定的移動性，需要支持功率有效性的路由協議。而客戶端參與轉發時最主要的是消耗自己的能量，這嚴重影響了它的壽命。為了激勵自私客戶端節點參與轉發，源客戶端支付給他一定的電子貨幣，每個客戶端可用賺取的電子貨幣支付給轉發自己業務的客戶端?？蛻舳酥饕蝿帐前l送自己的業務，而不是賺取電子貨幣。在不同電子貨幣數量和能量時一個客戶端轉發其他客戶端的傾向性是不同的：

1）當客戶端的電子貨幣較多而能量較少時，轉發其他客戶端業務的代價較高，它不是很愿意轉發其它客戶端的業務；當客戶端的電子貨幣較多而能量較多時，轉發其它客戶端業務的代價較低，它非常愿意轉發其它客戶端的業務。

2）當客戶端的電子貨幣較少而能量較少時，轉發其它客戶端業務的代價非常高，它很不愿意轉發其它客戶端的業務；當客戶端的電子貨幣較少而能量較多時，轉發其它客戶端業務的代價較高，它不很愿意轉發其它客戶端的業務。

總之，能量的重要性遠大于電子貨幣。借鑒文獻[6]的思想，代價函數的定義如下：

定義1當一個客戶端vi在具有電子貨幣Ci和能量Ei的條件下，轉發其它很業務量q而付出的代價與當前的能量Ei成反比，與當前電子貨幣Ci的對數和業務量q成正比，即：

這里，η為常量，作為一個參數在電子貨幣和能量之間的平衡因子，為了實現能量消耗均勻取值為16。在某一時間段內或某一時刻，可以認

1.3 粒子群算法綜述

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

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

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

慣性權重起到權衡局部最優和全局最優能力的作用。其中，wmax為初始權重；wmin為最終權重，itermax為最大迭代次數。這樣，粒子群算法在剛開始的時候傾向于開掘，然后逐漸轉向開拓，從而在局部區域調整解。

2 AODV路由協議

2.1 系統模型

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

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

S要給予中間客戶端一定的支付以激勵它們參與業務的轉發，并且這個支付要大于它付出的代價。在這個博弈中，每個vi選擇一個行動ai，這個行動是宣布它的當前可用帶寬和代價函數。因此，參與人的行動決定了代價函數fi（zi）和支付函數pi。因此，vi的效用函數是：

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

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

S要給予vi一定的支付以激勵它們參與業務的轉發。本文采用GSP拍賣，在S收到所有RREP以后，計算出P中每條路徑的代價并按照從小到大的順序進行排序，集合P變為LCP={PLCP1，PLCP2，…，PLCPm}（對于s≤t，那么Fs≤Ft）。如果客戶端vi位于PLCPj，那么給予客戶端vi的支付為：

2.1.2 附加約束條件

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

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

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

對上述不等式的兩邊同乘Fs）zt，從而系統模型變為GSP拍賣模型，即：

式（14）是模型的誠實性保證。顯然式（11）～（14）為一凸優化問題，直接用凸優化的方法進行求解可獲得帶寬和路由分配的結果，但是這樣會帶來大量的計算，尤其是（14）式。采用粒子群算法對上述的問題求解進行優化，可快速找到最佳分配結果。

2.2 基于GSP拍賣和粒子群優化的AODV路由分配算法

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

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

算法1利用粒子算法求解的基于GSP拍賣的路由分配算法

輸入：P中每條路徑的所有節點的可用帶寬和代價函數，P′中每條路徑的所有節點的可用帶寬。

輸出：P和P′中每條路徑的分配的帶寬以及所有節點的的支付。

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

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

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

3 結論

本文分析了自私WMN網絡中mesh客戶端的理性行為，并將其建模為GSP拍賣模型。然后提出了基于GSP拍賣和粒子群優化的AODV路由協議。此算法收斂速度較快，可以直接在客戶端側實現，協議簡單，可對AODV協議稍微修改就可應用到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，FU 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.