戴昊峰，何世彪，2，韓 輝，張 暉，2，譚 冕

(1.重慶通信學(xué)院重慶 400035;2.重慶大學(xué)通信學(xué)院重慶 400044)

無(wú)線ad hoc網(wǎng)絡(luò)采用分布式、自組織、無(wú)中心的架構(gòu)，可以很方便地應(yīng)用于不同場(chǎng)合，但是在網(wǎng)絡(luò)資源(主要是頻譜資源)有限的情況下，如何有效、公平地配置網(wǎng)絡(luò)資源，是ad hoc網(wǎng)絡(luò)在運(yùn)用時(shí)遇到的一個(gè)最為關(guān)鍵的問(wèn)題，也是目前尚未完全解決的問(wèn)題［1］。近期的研究表明，博弈論可以作為此類(lèi)問(wèn)題的有效分析工具［2－3］。根據(jù)用戶對(duì)網(wǎng)絡(luò)信息的掌握情況，可分為完美信息博弈和不完美信息博弈。所謂完美信息博弈是指參與者知道用戶沖突域內(nèi)每個(gè)設(shè)備所使用的信道，或者每個(gè)信道所分配的無(wú)線電。隨著無(wú)線射頻收發(fā)器硬件相關(guān)技術(shù)的迅速發(fā)展:一是無(wú)線網(wǎng)絡(luò)節(jié)點(diǎn)的射頻端已經(jīng)具備感知周?chē)畔⒌墓δ埽窃谝粋€(gè)無(wú)線網(wǎng)絡(luò)節(jié)點(diǎn)上裝備多個(gè)射頻器前端已經(jīng)成為廣泛的選擇。因此選擇基于完美信息博弈的多無(wú)線電信道分配在ad hoc網(wǎng)絡(luò)中具有可行性，在未來(lái)也有很大的發(fā)展前景，對(duì)它的研究有著重大的意義［4－5］。

目前，對(duì)于無(wú)線ad hoc網(wǎng)絡(luò)的信道分配機(jī)制主要分為集中式和分布式兩種，本文主要研究了分布式的信道分配機(jī)制。文獻(xiàn)［6］提出了一種最優(yōu)信道帶寬調(diào)制方法，利用一種“裝箱壓縮”方法并結(jié)合多無(wú)線電技術(shù)提出分布式流量感知的信道帶寬調(diào)制算法，有效地提高了頻譜使用率，但沒(méi)有考慮用戶獲取信道的公平性;文獻(xiàn)［7］中采用一種對(duì)每個(gè)節(jié)點(diǎn)分配同樣信道集合的方式，這種信道分配方式雖然易于實(shí)現(xiàn)，也能夠保證網(wǎng)絡(luò)的連通性，但不足以適應(yīng)復(fù)雜的網(wǎng)絡(luò)情況;文獻(xiàn)［8］中根據(jù)用戶獲取信息的不同提出了3種算法解決多無(wú)線電信道的分配問(wèn)題，3種算法都從不同方向?qū)崿F(xiàn)了自私節(jié)點(diǎn)向納什均衡點(diǎn)的收斂，并通過(guò)理論證明和仿真結(jié)果驗(yàn)證了第三種信道分配算法可以實(shí)現(xiàn)在網(wǎng)絡(luò)中達(dá)到納什均衡的目的，但該算法假設(shè)網(wǎng)絡(luò)場(chǎng)景為單沖突域，無(wú)法適應(yīng)多沖突域的網(wǎng)絡(luò)場(chǎng)景。文獻(xiàn)［9］在文獻(xiàn)［8］的基礎(chǔ)上提出了適合網(wǎng)絡(luò)場(chǎng)景為多沖突域的算法，算法假設(shè)兩跳范圍的用戶為沖突域內(nèi)，并以此為網(wǎng)絡(luò)中的各個(gè)自私節(jié)點(diǎn)以非合作博弈的方式對(duì)其無(wú)線電接口分配信道，最后仿真對(duì)比了單多沖突域的用戶平均傳輸速率，證明多沖突域情況更能最大化信道利用率，但是該算法復(fù)雜度較高，不易實(shí)現(xiàn)。針對(duì)以上算法的不足，本文提出一種較低復(fù)雜度的信道分配算法，用戶通過(guò)感知自身沖突域內(nèi)其他用戶的信道信息來(lái)選擇信道以達(dá)到納什均衡分配所需滿足的條件(即使效用函數(shù)最大)，仿真結(jié)果表明算法可以達(dá)到納什均衡點(diǎn)，并能夠較好地改善網(wǎng)絡(luò)性能(與單沖突域情況對(duì)比)。

1 系統(tǒng)模型

本文假設(shè)使用頻分復(fù)用(Frequency Division Multiple Access，F(xiàn)DMA)技術(shù)，將可用頻率分為相同帶寬的正交信道(在IEEE802.11a協(xié)議中有8條信道)。定義可用正交信道集合為C，可表示為

圖1 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

假設(shè)距離用戶兩跳及以內(nèi)的用戶為沖突域內(nèi)用戶，用戶可以感知自身沖突域內(nèi)用戶的信道信息。如圖1所示，用戶1的沖突域包含用戶2，3，9，10，即用戶1在信道分配時(shí)可以感知到上述用戶的完全信息。其他范圍為用戶1的沖突域外，此時(shí)假如用戶6使用與用戶1相同的信道則不會(huì)對(duì)用戶1產(chǎn)生干擾。

由于使用多無(wú)線電技術(shù)，用戶能夠同時(shí)使用多個(gè)信道進(jìn)行數(shù)據(jù)的傳輸，那么用表示用戶i的沖突域內(nèi)用戶i使用信道c∈Ci的無(wú)線電數(shù)目，Ci為用戶i使用的信道集合，有Ci?C，且該用戶所占用的所有無(wú)線電數(shù)目為，相應(yīng)的，用戶i的沖突域內(nèi)使用信道c的無(wú)線電數(shù)目為。基于以上假設(shè)，用戶i的信道分配策略可以表示為:，其中。從表示式可以看出，策略向量就是占用每個(gè)信道的用戶無(wú)線電數(shù)目，那么所有用戶的策略矩陣S可以表示為

式中:用S－i表示除用戶i外所有用戶的策略集合。

用戶i的用戶收益，即用戶所占用信道的帶寬(用戶傳輸速率)表示為Ui，由于用戶位于不同的沖突域，假如用戶j位于用戶i的沖突域內(nèi)，用戶j的無(wú)線電如果占用的信道為用戶i的無(wú)線電所占用的，那么它們將平分該信道總的帶寬，假設(shè)信道的帶寬不會(huì)因?yàn)闊o(wú)線電數(shù)目的增加而下降［9］，而對(duì)于用戶i沖突域外的用戶而言，使用相同的信道將不會(huì)對(duì)用戶i造成干擾。因此如果用戶i的無(wú)線電占用信道c，那么用戶i的無(wú)線電能獲得的帶寬為

2 多無(wú)線電信道分配策略的納什均衡

本節(jié)研究在多沖突域條件下博弈的納什均衡存在性的判定條件。首先引入納什均衡［2］的定義:

換句話說(shuō)，在一個(gè)已經(jīng)達(dá)到納什均衡的策略中，沒(méi)有用戶能夠通過(guò)單方面地改變用戶策略來(lái)改變用戶的收益。然而，納什均衡解可能存在兩種情況，一種是可能存在多個(gè)納什均衡解，二是納什均衡的解從系統(tǒng)模型來(lái)看不一定是最優(yōu)的。由此引出了帕累托最優(yōu)［2］的概念:

定義2:帕累托最優(yōu)(Pareto－Optimality)策略向量Spo是帕累托最優(yōu)的，假如存在S'使得式(5)成立

換句話說(shuō)，假如一個(gè)策略集合是帕累托最優(yōu)的，那么不存在其他策略集合s'使得至少有一個(gè)參與者的效用得到增加，而其他參與者的效用不會(huì)減少。

引理1:如果S*是一個(gè)多無(wú)線電多信道分配博弈的納什均衡策略，那么就有ki=k，?i成立。

引理1表明，一個(gè)理性用戶會(huì)使用所有無(wú)線電來(lái)增加自身的效用。

根據(jù)文獻(xiàn)［8］和［9］有以下定理成立，此定理有較強(qiáng)的適應(yīng)性，無(wú)論是在單沖突域還是多沖突域環(huán)境中都能成立，接下來(lái)本文所提算法將緊密?chē)@這個(gè)定理展開(kāi)。

定理1:信道分配策略S*是一個(gè)NE的，當(dāng)且僅當(dāng)滿足以下兩個(gè)條件:

由文獻(xiàn)［9］還可知假如信道c的帶寬函數(shù)R(kc)獨(dú)立于kc，?c∈C，那么NE信道分配策略S*一定是帕累托最優(yōu)的。也就是假如R(kc)的值不會(huì)隨著kc的變化而變化，那么得到的NE信道分配策略一定是最優(yōu)的。因此本文都假設(shè)R(kc)是獨(dú)立于kc。

3 信道分配算法描述

基于完美信息的信道分配算法要求用戶在信道分配前不僅知道自身的無(wú)線電所使用的信道情況，還要求用戶節(jié)點(diǎn)的無(wú)線電射頻端感知自身沖突域內(nèi)其他用戶的信息，以此來(lái)確定自身的信道策略使整體策略滿足定理1中的條件(使用戶自身效用函數(shù)達(dá)到最大值)。

算法最初進(jìn)行一次隨機(jī)信道分配，分配完成后，每個(gè)用戶感知自身沖突域內(nèi)每條信道c∈C上的無(wú)線電數(shù)目，并試圖通過(guò)重新組織分配信道給用戶的無(wú)線電接口來(lái)增大用戶總的傳輸速率。但是這個(gè)過(guò)程可能會(huì)出現(xiàn)一個(gè)問(wèn)題:很多用戶同時(shí)申請(qǐng)改變信道，這將會(huì)造成沖突，影響算法效率，延長(zhǎng)收斂時(shí)間。為此，本文將引入IEEE802.11的退避機(jī)制來(lái)解決這個(gè)問(wèn)題，首先定義一個(gè)退避窗口W，并且每個(gè)用戶以相同的概率從集合{1，2，…，W}中隨機(jī)選擇一個(gè)初始值作為退避計(jì)數(shù)器的值。然后在每一輪每個(gè)用戶都會(huì)將自身退避計(jì)數(shù)器值減1，當(dāng)退避計(jì)數(shù)器的值為0時(shí)用戶才能重新將信道分配給無(wú)線電，在用戶分配完信道后，又返回退避窗口W重置一個(gè)隨機(jī)值。這樣有效地避免了用戶間的沖突，增強(qiáng)了網(wǎng)絡(luò)整體性能。當(dāng)用戶的改變順序確定后，此時(shí)如果輪到用戶i∈N改變其信道，那么用戶i首先感知其沖突域內(nèi)有哪些用戶和其所有信道信息，將用戶i沖突域內(nèi)用戶記為，它是從所有用戶中提取出來(lái)的部分用戶的集合，記為用戶集合中使用次數(shù)最少的信道，表示用戶ii的無(wú)線電使用信道的數(shù)目，為用戶i的沖突域內(nèi)用戶使用信道的無(wú)線電數(shù)目，同理為為用戶i的沖突域內(nèi)用戶使用信道b的無(wú)線電數(shù)目。當(dāng)完成第一部分信道分配后此時(shí)用戶i的沖突域內(nèi)用戶已經(jīng)滿足定理1中第2個(gè)條件，但算法不一定滿足第1個(gè)條件，所以需要再次判斷分配。最后經(jīng)過(guò)多次循環(huán)可以達(dá)到整體的納什均衡點(diǎn)。

算法的流程圖如圖2所示。

圖2 算法流程圖

4 仿真分析

為了驗(yàn)證上述算法的相關(guān)性能，本小節(jié)設(shè)計(jì)了如下的仿真場(chǎng)景。用戶的拓?fù)浣Y(jié)構(gòu)如圖1所示，假設(shè)每條信道的吞吐量假設(shè)固定均為R(kc)=54 Mbit/s，由前文可知其不隨著無(wú)線電數(shù)目的增加而下降。退避窗口值W=20，編程語(yǔ)言為MATLAB。

圖3給出一個(gè)已達(dá)納什均衡點(diǎn)的信道分配結(jié)果，其中，用戶數(shù)目=10，每個(gè)用戶的無(wú)線電接口數(shù)目相同為k=3，正交信道數(shù)目為=8，從圖中可以看出，任何用戶在其沖突域內(nèi)的信道分配結(jié)果都滿足定理1的條件，達(dá)到了納什均衡。

圖4中用戶數(shù)目=10，每個(gè)用戶的無(wú)線電接口數(shù)目k=3，正交信道數(shù)目為=8，但是假設(shè)所有用戶在同一沖突域內(nèi)，并假設(shè)距離用戶兩跳及以內(nèi)的用戶為沖突域內(nèi)用戶，即用戶位于不同的沖突域中，圖示呈現(xiàn)了用戶在單沖突域和多沖突域中用戶收益的仿真對(duì)比，可以看出，用戶在多沖突域中具有更高的信道使用率。

圖3 一種納什均衡的信道分配結(jié)果

圖4 用戶在單多沖突域收益對(duì)比

圖5 算法執(zhí)行前后用戶收益的對(duì)比

圖6 不同的無(wú)線電數(shù)目對(duì)用戶收益的影響

圖7 不同信道數(shù)目對(duì)用戶收益的影響

5 結(jié)束語(yǔ)

眾所周知，無(wú)線ad hoc網(wǎng)絡(luò)的信道分配問(wèn)題一直都是一個(gè)NP難問(wèn)題，本文根據(jù)無(wú)線ad hoc網(wǎng)絡(luò)分布式的特點(diǎn)，引入博弈論的方法，提出了一種適用于多沖突域情況的完美信息信道分配算法，通過(guò)實(shí)驗(yàn)仿真與單沖突域的情況做出對(duì)比，驗(yàn)證了本文的算法可以更好地最大化信道的使用率，使網(wǎng)絡(luò)負(fù)載更加均衡。本文考慮的是完美信息，實(shí)際中由于硬件條件等達(dá)不到要求可能很難做到獲取完美信息，并且文中并沒(méi)有考慮多沖突域環(huán)境下可能存在的隱藏/暴露終端等問(wèn)題，因此下一步工作將考慮如果無(wú)法獲取完美信息應(yīng)該如何達(dá)到納什均衡并且兼顧隱藏/暴露終端問(wèn)題。

:

［1］汪濤.無(wú)線網(wǎng)絡(luò)技術(shù)導(dǎo)論［M］.北京:清華大學(xué)出版，2009.

［2］SRIVASTAVA V，NEEL J O，MACKENZIE A B，et al.Using game theory to analyze wireless ad hoc networks［J］.IEEE Communications Surveys and Tutorials，2005，7(1/4):46－56.

［3］彭文藝，饒志強(qiáng)，吳濤.博弈論在無(wú)線自組網(wǎng)技術(shù)中的應(yīng)用［J］.計(jì)算機(jī)與數(shù)字工程，2006，34(6):117－119.

［4］BAHL V，ADYA A，PADHYE J，et al.Reconsidering the wireless LAN platform with multiple radios［C］//Proc.Workshop on Future Directions in Network Architecture.［S.l.］:IEEE Press，2003.

［5］YANG D，F(xiàn)ANG X，XUE G.Channel allocation in non－cooperative multi－radio multi－channel wireless networks［C］//Proc.IEEE INFOCOM.Orlando，F(xiàn)L:IEEE Press，2012:882－890.

［6］RANIWALA A，CHIUEH T.Architecture and algorithms for an IEEE 802.11－based multi－channel wireless mesh network［C］//Proc.24th Annual Joint Conference of the IEEE Computer and Communications Societies.New York:IEEE Press，2005:2223－2234.

［7］DRAVES R，PADHYE J，ZILL B.Routing in multi－radio，multi－h(huán)op wireless mesh networks［C］//Proc.10th Annual International Conference on Mobile Computing and Networking.［S.l.］:ACM Press，2004:114－128.

［8］FELEGYHAZI M，CAGALJ M，BIDOKHTI S S，et al.Non－cooperative multi－radio channel allocation in wireless networks［C］//Proc.26th IEEE International Conference on Computer Communications.［S.l.］:IEEE Press，2007:1442－1450.

［9］KIM H K，LEE T J.CHASS－M:channel assignment for fair payoff based on game theory for wireless multi－h(huán)op networks［C］//Proc.4th International Conference on Innovations in Information Technology.Dubai:IEEE Press，2007:282－286.

［10］史佳佳，劉宴兵.多射頻無(wú)線網(wǎng)絡(luò)中多信道分配方法的研究［J］.計(jì)算機(jī)應(yīng)用研究，2012，29(6):2290－229.

［11］鄭鵬宇，何世彪，戴昊峰，等.基于最大化網(wǎng)絡(luò)吞吐量的WMN信道分配算法［J］.電視技術(shù)，2013，37(19):176－180.