容量受限網絡選擇中的時延影響分析*

張冬梅，隨楠楠，王 聰，鐘 衛

(解放軍理工大學通信工程學院，江蘇 南京 210007)

0 引言

在未來異構融合的無線網絡環境下，移動用戶借助于多模終端，可在多個可用的接入網絡之間進行切換［1－2］，網絡選擇作為網絡切換的先決條件，將發揮著重要的作用。網絡選擇的目標一是根據“ABC”準則［3］尋求最佳的接入機會，另一個則是起到均衡負載的作用。

異構無線網絡之間有著廣泛的差異性，這使得傳統上基于接收信號強度的網絡選擇算法不再適用了。N.Baldo等人在文獻［4］中使用了一種模糊判決方法，將用戶對業務的服務質量(QoS)需求與估計到的候選網絡的傳輸層性能比較，用戶選擇滿意度最高的候選網絡。E.Stevens－Navarro等人在文獻［5］中使用馬爾科夫判決過程(MDP)方法綜合考慮了切換報酬和切換代價來進行網絡選擇，盡可能降低網絡切換頻率。

網絡選擇實際上也是移動用戶之間對有限無線資源的競爭，因此博弈論方法非常適用于解決這一類問題［6］。在眾多博弈方法中，進化博弈理論(EGT)引入了種群的概念，對種群的策略分布和動態演進過程進行研究，非常適合分析大規模網絡系統中的資源管理等問題。D.Niyato等人在文獻［7］中將進化博弈用于網絡選擇，最終使得種群內每個用戶的收益都不低于種群的平均收益。

負載均衡是網絡運維管理的重要內容之一，網絡運營商為了向用戶提供帶有QoS保證的服務，通常會對用戶容量做出一定的限制。此外，用戶在進行網絡選擇時，信息的獲取往往是有延時的，這會對用戶的行為產生重要影響。目前，關于網絡受限條件下的時延對網絡選擇的影響的研究還比較少。

文中在一個受限的異構網絡環境下，基于進化博弈理論針對網絡時延對用戶網絡選擇行為的影響進行研究。文中設計了帶有懲罰項的收益函數，使得理性用戶不去選擇不可行的策略，即使受到延時信息的誤導，理性用戶也能逐步演進到均衡狀態。文中設計了一種集中式的進化博弈實現算法，數值和仿真結果驗證了所提收益函數和算法的有效性。

1 系統模型

如圖1所示，文中考慮了一個由無線城域網(WMAN)、蜂窩網絡和無線局域網(WLAN)交錯重疊構成的異構無線接入環境。

圖1 用戶容量受限的異構網絡環境Fig.1 Capacity constrained heterogeneous networks

由于WLAN網絡的開放性和較高的帶寬，對移動用戶有著較大的吸引力，文中假定WLAN為了保證QoS而對用戶容量做了限制，當用戶數超過門限時，WLAN將因為負載過重而性能急劇惡化。文中設定移動用戶具有相同的業務類型，接入同一網絡中的用戶將獲得相同的可用帶寬，并以可用帶寬和負載表征用戶的收益。用戶在進行網絡選擇時獲取的信息通常是有延時的，文中假定所有用戶的時延是相同的。

2 帶時延的進化博弈建模

博弈模型一般包括三個組成部分:參與者、策略和收益。進化博弈理論則引入了生物學中的種群概念，側重于研究群體之間對于資源的競爭行為。

對于同一業務類型的移動用戶來說，處于同一區域的用戶就構成了一個種群，種群成員具有相同的策略空間和利益關系，不同種群之間具有競爭關系。假如我們用{wm，ce，wl}分別表示WMAN、蜂窩網和WLAN，那么區域1中的用戶構成了種群1，其策略空間是{wm};區域2中的用戶構成了種群2，其策略空間是{wm，ce};區域3中的用戶構成了種群3，其策略空間是{wm，ce，wl}。

設 i={wm，ce，wl}代表接入網絡，a={1，2，3}表示區域或者種群，設Na表示種群a中的用戶數表示種群a中選擇網絡i的用戶數，則表示種群a中選擇網絡i的用戶數占整個種群的比例，那么種群在t時刻的狀態就可以用矢量X(t)=來表示。特別的，由于易推知，且種群1中的用戶只能接入WMAN(即=1)，那么文中就選用矢量來描述種群的分布狀態。

設Ai表示網絡i的覆蓋區域集合，Ni表示接入網絡i的總用戶數，Ci是網絡i的全部可用帶寬。設表示種群a中選擇網絡i的用戶所能獲得的收益，對未設限的WMAN和蜂窩網絡來說，接入其中的用戶可獲得的收益為:

式中，ui是收益因子，pi是代價因子，式(1)的第二項表明網絡負載越高，用戶的收益越低。

式中，Θ(s)=0，s≥0，Θ(s)=s，s＜0;βwl是一個正常量，表示懲罰因子，只有當βwl足夠大，用戶可能因WLAN容量超限而受到嚴厲懲罰時，理性用戶才不會選擇不可行的策略。

種群中的用戶通過觀察采取不同策略的用戶所獲得的回報來決定自身的行為，種群中的用戶是有界理性地，他只是選擇一個策略使其自身收益不低于種群的平均回報，而不是尋求接入收益最高的網絡。從生物學的角度看，進化博弈中用戶的策略選擇就是一種模仿行為，在理論上用一組模仿者動態微分方程來分析種群的演進過程［7］。實際中用戶獲取的信息具有時延τn，那么用戶在t時刻只能依據t－τn時刻的歷史信息做出網絡選擇判決，帶有延時的模仿者動態微分方程為:

在參數給定的條件下，將式(1)和式(2)代入到式(3)中可以準確的推導出任意時刻的種群狀態，這一點是進化博弈理論的很大優勢。如果種群最終能夠達到一種穩定狀態，種群的分布不再變動，那么這種狀態就稱為進化均衡態，是進化博弈的解。

模仿者動態方程表明成功的策略在種群中擴散的更快。基于式(1)和式(2)所設計的收益函數，在帶時延的受限網絡選擇情境中，WLAN能使用戶獲得較高收益，有較多的用戶通過觀察和模仿選擇了接入WLAN，從而使得WLAN的用戶量迅速接近門限值。在此情形下，其他用戶只能在WMAN和蜂窩網絡中做出選擇，直到接入兩種網絡獲得的收益相等。最終種群達到進化均衡態時，應有:

3 集中式的進化博弈算法實現

假設用戶可獲得當前所處服務區域內的可用接入網絡信息，能夠觀察種群內其他用戶的策略和收益，那么用戶就可做出較為準確的網絡選擇，這通過IEEE 802.21定義的媒介獨立切換信息服務是可以實現的［9］。進化博弈算法通過迭代實現，其關鍵問題是如何確定迭代步長。觀察式(3)可以得到

由微積分性質可以知道t時刻在Δt時間內種群分布的變化為

設種群a中選擇網絡i的用戶有相同的切換概率p，t時刻發生切換的用戶數K便是服從二項分布的隨機變量，即，其期望即為:

假設迭代時延為τs，那么用戶在第l次迭代只能依據第l－τs次迭代的歷史信息進行網絡選擇。因此帶時延的集中式進化博弈算法實現如圖2所示。

圖2 帶時延的集中式進化博弈網絡選擇算法Fig.2 Centralized EGT－based network selection algorithm with iteration delay

4 數值與仿真分析

在仿真中我們設定WMAN，WLAN和蜂窩網絡的帶寬分別為10 Mb/s、7 Mb/s和2 Mb/s;每個種群的用戶數分別為N1=10，N2=20，N3=30;設定收益函數中的參數為 ui=1，pi=0.01，βwl=10;模仿者動態方程中的參數為σ=1。

圖3為網絡時延 τn=0.5 s時，由式(3)和式(4)所得到的種群的進化均衡解和種群演進軌跡。由圖可以看出，種群的進化均衡態不止一個，種群處于不同起始狀態時，將沿著不同的演進軌跡趨向于不同的進化均衡態。從圖3可以看出，當網絡存在時延時，即使，用戶仍可能依據歷史信息選擇切換到WLAN網絡，造成用戶收益的急速下降;而WLAN性能的惡化又迫使WLAN用戶選擇切換到WMAN和蜂窩網絡，使得WLAN的性能得到改善。這樣種群受到時延的影響便處于一種震蕩調整的過程，并逐步演進到均衡狀態。

圖3 τn=0.5 s時種群的進化均衡解和演進軌跡Fig.3 Evolutionary equilibria and populations’evolutionary trajectories when τn=0.5 s

圖4和圖5是在迭代時延為τs=1，步長分別為Δ=1和Δ=3的條件下，通過仿真所得到的種群分布動態演進過程。由圖4可以看出，Δ=1時種群在演進過程中的波動幅度較小，最終種群可以進化到較為穩定的狀態，但是演進需要較長的時間。由圖5可以看出，在Δ=3時種群可以很快的進入一種有規律的震蕩狀態，但是震蕩幅度很大，種群無法進入均衡狀態。由兩圖的對比可以得出結論，當網絡存在時延時，較小的迭代步長可以使得種群在震蕩調整中逐步演進到均衡狀態，但需要較長的時間;較大的迭代步長可以加速種群的演進過程，但步長過大也使得種群的調整幅度過大，可能無法演進到均衡狀態。

圖4 τs=1，Δ=1時種群分布動態演進過程的仿真結果Fig.4 Simulated results of populations’dynamic evolution process when τs=1，Δ=1

圖5 τs=1，Δ=3時種群分布動態演進過程的仿真結果Fig.5 Simulated results of populations’dynamic evolution process when τs=1，Δ=3

圖6和圖7是在步長為Δ=1，迭代時延分別為τs=1和τs=2的條件下，通過仿真得到的種群收益的動態演進過程。由兩圖可以看出，由于受到網絡時延的影響，WLAN網絡的收益在震蕩中逐步趨于均衡狀態。τs=1時，種群收益可以較快的通過迭代進入均衡狀態，但τs=2因時延較大，用戶受錯誤歷史信息的影響也更大，因而用戶收益的下降更為劇烈，收益波動幅度也更大，用戶收益演進到均衡狀態所需時間更長。

圖6 τs=1，Δ=1時種群收益動態演進過程的仿真結果Fig.6 Simulated results of populations’utility evolution process when τs=1，Δ=1

圖7 τs=2，Δ=1時種群分布動態演進過程的仿真結果Fig.7 Simulated results of populations’utility dynamic evolution process when τs=2，Δ=1

5 結語

在用戶容量受限的異構網絡環境下，文中研究了時延對網絡選擇影響的問題。文中將問題建模成一個帶時延的進化博弈，設計了一種懲罰收益函數，使得理性用戶不去選擇不可行的策略。然后文中設計了一種集中式的進化博弈實現算法，通過數值和仿真分析，驗證了所提算法和收益函數的有效性。仿真結果表明，時延和迭代步長對種群動態演進過程有著重大的影響，在網絡選擇算法的設計中必須予以重視。

［1］劉睿強，林濤.3G邊緣問題小區切換策略的探討［J］.通信技術，2011，44(03):129－131.LIU Rui－qiang，LIN Tao.Discussion on Handover Strategy of 3G Marginal Bad Cells［J］.Communications Technology，2011，44(3):129－131.

［2］孫俊杰，鄢妍.3G移動通信技術的研究［J］.通信技術，2012，45(04):66－67.SUN Jun－jie，YAN Yan.Study on 3G Mobile Communication Technology［J］.Communications Technology，2012，45(4):66－67.

［3］GUSTAFSSON E，JONSSON A.Always Best Connected［J］.IEEE Wireless Commun.，2003，10(01):49－55.

［4］BALDO N，ZORZI M.Cognitive Network Access Using Fuzzy Decision Making［J］.IEEE Transactions on Wireless Communications，2009，8(07):3523－3535.

［5］STEVENS－NAVARRO E，LIN Y，WONG S W V.An MDP－based Vertical Handoff Decision Algorithm for Heterogeneous Wireless Networks［J］.IEEE Trans.Veh.Technol.，2008，57(02):1243－1254.

［6］TRESTIAN R，ORMOND O，MUNTEAN G.Game Theory－Based Network Selection:Solutions and Challenges［J］.IEEE CommunicationsSurveys＆Tutorials，2012，14(04):1212－1231.

［7］NIYATO D，HOSSAIN E.Dynamics of Network Selection in Heterogeneous Wireless Networks:An Evolutionary Game Approach［J］.IEEE Trans.Veh.Technol.，2009，58(04):2008－2017.

［8］ZHONG W，XU Y，HUAGLORY T.Game－theoretic Opportunistic Spectrum Sharing Strategy Selection for Cognitive MIMO Multiple Access Channels［J］.IEEE Trans.Signal Process.，2011，59(06):2745－2759.

［9］TANIUCHI K.IEEE 802.21:Media Independent Handover:Features，Applicability，and Realization［J］.IEEE Commun.Magazine，2009，47(01):112－120.