基于議價博弈的衛(wèi)星網(wǎng)絡(luò)時隙分配算法

尹 譯，梁 俊，肖 楠，王 軼，鐘 贇

（空軍工程大學(xué) 信息與導(dǎo)航學(xué)院，陜西 西安710077）

0 引 言

隨著衛(wèi)星通信技術(shù)的不斷發(fā)展，業(yè)務(wù)傳輸QoS要求的提高與通信資源有限之間的矛盾日益突出，高效的衛(wèi)星資源管理機制可以在滿足用戶傳輸需求的同時提高通信資源利用率，是衛(wèi)星通信中需要解決的一個關(guān)鍵問題。資源管理問題的本質(zhì)在于如何解決多個用戶對通信資源的競爭，通過制定合理的資源分配方案，達到最優(yōu)分配效能。作為解決競爭問題的典型理論，博弈論在資源調(diào)度領(lǐng)域被廣泛應(yīng)用［1］，通過建立相應(yīng)模型有效地解決了某些資源競爭問題。文獻 ［2］在協(xié)作博弈模型的基礎(chǔ)上，提出分布式頻譜的共享方法，解決了信道共享的問題；Niyato［3，4］在認知網(wǎng)絡(luò)中定義多用戶競爭主用戶頻段的效用函數(shù)，并基于此提出議價博弈的頻譜價格問題；文獻 ［5］對自私性CR 網(wǎng)絡(luò)中的協(xié)作功率分配問題進行建模研究，通過求解納什議價解，使節(jié)點間達到共贏的效果。文獻 ［6］設(shè)計動態(tài)的二級博弈架構(gòu)，實現(xiàn)了優(yōu)化主次用戶頻率租借決策的目的。

目前博弈論應(yīng)用研究主要關(guān)注功率和頻率，對于時隙分配討論較少。在MF－TDMA 衛(wèi)星通信網(wǎng)絡(luò)中，業(yè)務(wù)優(yōu)先級差異引起的時隙分配公平性問題［7］是網(wǎng)絡(luò)所面臨的問題之一。針對該問題，本文引入博弈論觀點，通過構(gòu)建合理的收益模型，求解出系統(tǒng)最大收益點，并設(shè)計基于議價博弈的分配算法，在最大收益點的基礎(chǔ)上獲得理想的分配方案，提高業(yè)務(wù)間的公平性，改善低等級業(yè)務(wù)的服務(wù)質(zhì)量。

1 衛(wèi)星網(wǎng)絡(luò)時隙分配問題

在MF－TDMA 衛(wèi)星網(wǎng)絡(luò)中，不同用戶通過時隙分配的方式共享信道，如圖1所示，由衛(wèi)星根據(jù)時隙申請進行分配，用戶利用時隙完成信息傳輸，實現(xiàn)多個用戶對同一載波信道的共享。為保證通信質(zhì)量，用戶希望獨享盡可能多的時隙，但受制于可分配時隙數(shù)目，用戶獲得的時隙有限，因此出現(xiàn)時隙的競爭行為。

圖1 MF－TDMA 共享信道

根據(jù)業(yè)務(wù)QoS要求差異，ITU－T I.356標準將網(wǎng)絡(luò)中業(yè)務(wù)分為恒定比特率CBR 業(yè)務(wù)、可變比特率VBR 業(yè)務(wù)、可用比特率ABR 業(yè)務(wù)、未定比特率UBR 業(yè)務(wù)，其中CBR、VBR、ABR 業(yè)務(wù)有嚴格的QoS要求，屬于高等級業(yè)務(wù)，而UBR 業(yè)務(wù)則沒有相關(guān)要求，屬于低等級的盡力而為 （best efforts）業(yè)務(wù)。在具體時隙分配中，VBR 業(yè)務(wù)流速率可變且難以預(yù)測，系統(tǒng)為保證QoS，優(yōu)先為其分配時隙資源，UBR 業(yè)務(wù)流則利用剩余時隙進行傳輸。這種分配的不公平嚴重損害了UBR 業(yè)務(wù)傳輸性能，特別是當VBR 業(yè)務(wù)流出現(xiàn)突發(fā)業(yè)務(wù)時，剩余時隙被過度占用，UBR 業(yè)務(wù)流緩沖隊列增大，時延提高，某些情況下甚至造成阻塞。

上述時隙競爭的公平性問題可抽象為博弈參與者利益分配問題，通過借鑒議價博弈模型中出價—妥協(xié)—出價機制解決，使業(yè)務(wù)間做出合理讓步，最終形成各業(yè)務(wù)均能接受的時隙分配方案，這是本文的出發(fā)點。

作為一種典型合作性博弈，議價博弈［7］假設(shè)參與者們雖存在利益沖突，但可以通過相互協(xié)商達成互惠的結(jié)果。議價博弈的進程可被描述為：

（1）議價周期開始，競拍者A 向競拍者B 提出利益分配方案。

（2）若B接受，議價周期結(jié)束，分配方案形成。若B不接受，向A 提出新的分配方案。

（3）若A 接受，議價周期結(jié)束，分配方案形成。若A不接受，開始新的議價周期。

根據(jù)無名氏定理 （folk theorem）［8］可以證明，在數(shù)輪的議價之后，最終的定價方案帶來的收益能夠達到A、B理性條件［9］下可行收益。

2 基于議價博弈的模型建立

2.1 網(wǎng)絡(luò)模型

假設(shè)用戶和衛(wèi)星之間的往返時延為τ，用戶 （假定每個用戶只傳輸單類型的業(yè)務(wù)流）在t 時刻獲得的時隙數(shù)n（t）實際是衛(wèi)星對t－τ時刻發(fā)送的時隙請求n（t－τ）的響應(yīng)，這種固有長時延τ的存在使用戶與衛(wèi)星間無法頻繁交互博弈信息，不能滿足議價博弈對于完全信息［10］的要求，故需在星上為用戶配置代理，代替用戶進行博弈，如圖2所示。

圖2 博弈代理的設(shè)置

業(yè)務(wù)的緩存隊列長度是星上代理在博弈中選擇行為的依據(jù)，能反映業(yè)務(wù)到達的速率以及擁塞狀態(tài)。由于星地交互時延，用戶不能實時向衛(wèi)星告知隊列長度L（t），只能由星上代理根據(jù)已掌握信息完成有關(guān)隊列狀態(tài)的推斷。下面介紹一種適用于星上代理的地面緩存隊列狀態(tài)的估計方法。

式中：narr（t）——t時刻到達隊列的待發(fā)送信元數(shù)。

隊列增量ΔL從時隙的需求和分配角度估計地面緩存隊列的狀態(tài)，若ΔL 較大，表明隊列長度增加，用戶時延增大，可能出現(xiàn)擁塞；若ΔL 較小，表明用戶緩存隊列空閑，可以適當為其他用戶提供時隙。在博弈過程中，代理根據(jù)ΔL 值決定可妥協(xié)程度，使議價完全基于傳輸需求，避免業(yè)務(wù)類型差異帶來不公平。

2.2 收益模型

博弈論定義收益是指參與者通過執(zhí)行策略所獲得的利潤。本文中系統(tǒng)獲得的收益包括：①經(jīng)濟收益，即系統(tǒng)為用戶提供傳輸服務(wù)需收取一定的利潤；②社會影響，指用戶給予系統(tǒng)正面或負面的評價及在行業(yè)內(nèi)產(chǎn)生的連鎖效應(yīng)。同理，用戶在使用衛(wèi)星實現(xiàn)業(yè)務(wù)傳輸時，也會為其自身帶來相應(yīng)的經(jīng)濟收益和社會影響。

衛(wèi)星通信系統(tǒng)中，用戶通過向系統(tǒng)申請時隙實現(xiàn)其數(shù)據(jù)傳輸，在這個過程中，衛(wèi)星系統(tǒng)和用戶都需要考慮各自收益。為了達到系統(tǒng)收益最大化，設(shè)其收益是關(guān)于為不同用戶i分配時隙數(shù)ni的函數(shù)，構(gòu)造以下系統(tǒng)收益函數(shù)

式中：c——待定變量，表示衛(wèi)星 “出售”單位時隙的成本，包含系統(tǒng)損耗、功率開銷等方面；pi——用戶i “購買”單位時隙所支付給系統(tǒng)的價格。時隙價格一方面與用戶需求滿足程度相關(guān)，另一方面受到用戶間的公平性影響，故時隙價格是關(guān)于分配時隙數(shù)ni的函數(shù)pi（ni）。

在經(jīng)濟學(xué)中，量化偏好間的相對關(guān)系采用序數(shù)效用，其描述模式［13］有完全替代模式、完全互補模式、準線性偏好模式、柯布—道格拉斯偏好模式。由于需求滿足程度和用戶公平性處于可相互替代關(guān)系，故按照完全替代模式構(gòu)造單位時隙價格函數(shù)

衡量用戶間的公平性。

當用戶獲得n 個時隙進行業(yè)務(wù)傳輸，帶來相應(yīng)收益，而付出的代價是時延對于業(yè)務(wù)質(zhì)量的影響。定義用戶收益函數(shù)

2.3 最佳收益點

在2.2節(jié)建立的系統(tǒng)收益模型中，衛(wèi)星可以通過調(diào)節(jié)用戶分配時隙數(shù)來獲得最佳收益。為了便于研究系統(tǒng)最佳收益點及相應(yīng)條件，假定參加時隙分配只有2個用戶，令U′SS（n1，n2）＝0 可解得系統(tǒng)收益最大的時隙分配方案

解得

條件 （10）不成立時，（n1，n2）＝（n）無法在約束條件n1＋n2≤L 下取得，用戶間形成時隙競爭，由星上代理代替用戶進行議價，最終形成雙方接受的分配方案。

3 時隙分配算法

當衛(wèi)星不能提供（nA，nB）＝（n）的分配方案時，由用戶的星上代理進行時隙競爭，通過博弈最終產(chǎn)生令雙方都接受的時隙的分配方案。用戶議價博弈過程可以用圖3中算法框架描述。

圖3 議價博弈過程的算法

由于衛(wèi)星處理分配的時間有限，數(shù)個失敗的議價周期會導(dǎo)致待分配的時隙無法被利用，系統(tǒng)和用戶均不能獲得收益。所以在單個不成功的議價周期后，用戶再次提出的分配方案時應(yīng)進行某種程度的 “妥協(xié)”。描述妥協(xié)可引入博弈論中貼現(xiàn)因子δ（0＜δ＜1），根據(jù)文獻 ［7］的解釋，δ體現(xiàn)博弈參與人的耐心程度，其值越大說明議價的耐心越大，做出的妥協(xié)越小。用戶A 在第k＋1次出價為

在決定是否接受A 所提分配方案時，用戶代理由式（4）、式 （9）計算分配方案（nA，k＋1，L－nA，k＋1）對應(yīng)的收益（UA，UB），將UB與B所期望收益U′B比較，有

4 仿真及結(jié)果分析

與傳統(tǒng)分配算法優(yōu)先保證高等級業(yè)務(wù)流所不同，本文所提時隙分配算法側(cè)重于提升業(yè)務(wù)間的公平性，從而改善低等級業(yè)務(wù)的服務(wù)質(zhì)量。為了驗證該算法在系統(tǒng)中的性能，設(shè)置時隙獲得數(shù)與請求數(shù)的比值和緩存隊列長度2個指標，前者衡量時隙分配的公平性，后者反映業(yè)務(wù)的發(fā)送速率及擁塞程度，構(gòu)建如下仿真環(huán)境：

用戶A、B在MF－TDMA 衛(wèi)星網(wǎng)絡(luò)中利用某信道進行傳輸服務(wù)，其中A 以VBR 方式發(fā)送一段MPEG－4格式視頻，每幀大小分布如圖4所示；B以UBR 方式進行文件數(shù)據(jù)上傳，限定上傳峰值速率不超過1 Mbps。

圖4 視頻幀大小分布

每幀中可供分配時隙總數(shù)L＝30，幀長40ms，信道最大速率3 Mbps。約定A、B的議價博弈貼現(xiàn)因子

由式 （4）可知，在n＜n 時，收益U 是分配時隙數(shù)n的單調(diào)增函數(shù)，故仿真中采用n 等價代替U。設(shè)定用戶接受議價的收益條件

仿真通過上述信道傳輸用戶A、B 數(shù)據(jù)，時隙分配采用基于議價博弈的分配算法；同時在另一相同系統(tǒng)中采用加權(quán)輪詢 （weighted round robin）的分配方式，作為對照組進行實驗。仿真結(jié)果如圖5～圖7所示。

圖5 UBR 業(yè)務(wù)時隙供需比nB／n～B

圖6 UBR 業(yè)務(wù)緩沖區(qū)隊列長度

圖7 VBR 業(yè)務(wù)緩沖區(qū)隊列長度

由圖5可知，加權(quán)輪詢分配算法不能有效滿足UBR 業(yè)務(wù)的時隙請求，特別是當用戶A 出現(xiàn)突發(fā)業(yè)務(wù)時 （1～16幀），VBR 業(yè)務(wù)占據(jù)所有時隙，UBR 業(yè)務(wù)傳輸停滯，極大損害了業(yè)務(wù)間公平性。而基于議價博弈的時隙分配算法的值集中在1附近，即使出現(xiàn)VBR 突發(fā)業(yè)務(wù)，只造成短暫下降，不會中斷UBR 業(yè)務(wù)傳輸，使UBR 業(yè)務(wù)獲得較好的傳輸性能。這是因為加權(quán)輪詢分配算法優(yōu)先滿足高權(quán)重VBR 業(yè)務(wù)流的時隙請求，低權(quán)重UBR 業(yè)務(wù)流只能使用部分剩余時隙，無法獲得可靠的傳輸性能保證；而在基于議價博弈的時隙分配算法中，分配依據(jù)是傳輸需求而不是業(yè)務(wù)優(yōu)先級，確保時隙分配給最需要的業(yè)務(wù)流，避免高等級業(yè)務(wù)在輕負載下過度占用時隙，改善了業(yè)務(wù)間的公平性。

圖6、圖7分別是2種分配算法下UBR、VBR 業(yè)務(wù)的緩沖區(qū)隊列長度。從圖6可以看出，基于議價博弈的分配算法能有效減少UBR 業(yè)務(wù)緩沖區(qū)隊列長度和擁塞概率，提高傳輸速率，避免突發(fā)VBR 業(yè)務(wù)造成傳輸速率波動，改善用戶的服務(wù)質(zhì)量。在圖7中，基于議價博弈的分配算法緩沖區(qū)隊列長度變化趨勢與加權(quán)輪詢分配算法相同，表明其傳輸速率仍能根據(jù)業(yè)務(wù)的到達速率進行調(diào)整，對突發(fā)業(yè)務(wù)擁有良好的適應(yīng)性。但是，VBR 業(yè)務(wù)傳輸性能出現(xiàn)部分下降，這是由于在議價過程中用戶A 存在 “妥協(xié)”行為，減少了對時隙的需求。

5 結(jié)束語

針對MF－TDMA 衛(wèi)星時隙分配公平性問題，本文從博弈論的觀點出發(fā)，構(gòu)建相應(yīng)的網(wǎng)絡(luò)結(jié)構(gòu)和收益模型，并討論系統(tǒng)最大收益的存在性問題，最終提出一種基于議價博弈的時隙分配算法。在該算法中，業(yè)務(wù)流之間在最大受益點的基礎(chǔ)上，依據(jù)實際需求進行議價博弈，通過合理妥協(xié)退讓，形成理想的分配方案。為使衛(wèi)星能夠克服長時延估計業(yè)務(wù)緩沖區(qū)隊列狀態(tài)，還設(shè)計了相應(yīng)的隊列長度估計方法。算法雖然沒有明確考慮業(yè)務(wù)類型的優(yōu)先級，但卻將優(yōu)先級包含在議價得可妥協(xié)程度中，不違背ITU 所提倡的業(yè)務(wù)分類原則。仿真結(jié)果表明，該算法以高等級業(yè)務(wù)性能部分下降為代價，有效提升業(yè)務(wù)間公平性，大幅改善低等級業(yè)務(wù)的服務(wù)質(zhì)量。但是，本文僅討論了算法在包含2個用戶的系統(tǒng)中的性能，對于多用戶系統(tǒng)的研究有待于以后完善。

［1］XU Li.Applications of game theory in wireless communication network ［M］.Beijing：Science Press，2012 （in Chinese）.［許力.博弈理論在無線網(wǎng)絡(luò)中的應(yīng)用 ［M］.北京：科學(xué)出版社，2012.］

［2］Suris JE.Cooperative game theory for distributed spectrum sharing ［C］／／IEEE International Conference on Communications，2007：5282－5287.

［3］Niyato D，Hossain E.Competitive spectrum sharing in cognitive radio networks：A dynamic game approach ［J］.IEEE Transactions on Wireless Communications，2008，7 （7）：88－94.

［4］Niyato D，Hossain E.Competitive pricing for spectrum sharing in cognitive radio networks：Dynamic game，inefficiency of nash equilibrium，and collusion ［J］.IEEE Journal on Selected Areas of Communications，2008，26 （1）：192－202.

［5］LIU Peng.Performance improvement algorithms based on bar－gaining game theory for wireless cooperative relay networks［J］.Telecommunication Engineering，2012，52 （5）：770－775（in Chinese）.［劉鵬.基于議價博弈論的無線協(xié)作中繼網(wǎng)絡(luò)性能改進算法 ［J］.電訊技術(shù)，2012，52 （5）：770－775.］

［6］Zhu Kun，Niyato D.Dynamic spectrum leasing and service selection in spectrum secondary market of cognitive radio networks［J］.IEEE Transactions on Wireless Communication，2012，11 （3）：1136－1145.

［7］ZHANG Weiying.Game theory and information economics［M］.Shanghai：Shanghai People’s Publishing House，2012（in Chinese）. ［張維迎.博弈論與信息經(jīng)濟學(xué) ［M］.上海：上海人民出版社，2012.］

［8］Le Treust M，Lasaulce S.A repeated game formulation of energy－efficient decentralized power control ［J］.IEEE Transactions on Wireless Communications，2010，9 （9）：2860－2869.

［9］JIANG Junli.Logic study of epistemic and rational conditions of some game－theoretic solutions［J］.Computer Science，2010，37（5）：223－227（in Chinese）.［蔣軍利.對博弈解概念認知和理性條件的邏輯分析［J］.計算機科學(xué)，2010，37 （5）：223－227.］

［10］Aumann RJ.Backward induction in games of perfect informa－tion ［C］／／27th Annual ACM／IEEE Symposium on Logic in Computer Science，2012：1－2.

［11］Vassaki S，Panagopoulos AD，Constantinous Philip，et al.Market－based bandwidth allocation for broadband satellite communication networks ［C］／／Second Conference on Advances in Satellite and Space Communications，2010：110－115.

［12］QIN Yong.MAC protocol based on bandwidth on demand（BoD）in DVB－RCS satellite communication systems ［J］.Journal of Astronautics，2010，31 （3）：838－843 （in Chinese）. ［秦勇.基于帶寬按需分配的DVB－RCS 寬帶衛(wèi)星MAC協(xié)議 ［J］.宇航學(xué)報，2010，31 （3）：838－843.］

［13］LI Wenbian.A microeconomics based dynamic spectrum management algorithm for cognitive wireless networks ［J］.Journal of Electronics ＆Information Technology，2009，31（4）：897－902 （in Chinese）.［黎文邊.認知無線網(wǎng)絡(luò)中基于微觀經(jīng)濟學(xué)的動態(tài)頻譜管理算法 ［J］.電子與信息學(xué)報，2009，31 （4）：897－902.］

［14］Simeon O，Gunduz D，Poor HV，et al.Compound multipleaccess channels with partial cooperation ［J］.IEEE Transactions on Information Theory，2009，55 （6）：2425－2441.