一種AdHoc網絡的MAC層信道動態分配方法

2023-06-04 15:04:01

專利名稱：一種Ad Hoc網絡的MAC層信道動態分配方法
技術領域：
本發明屬於Ad Hoc網絡領域，涉及一種無線MAC層多信道動態分配方法。
背景技術：
Ad Hoc網絡由一組可隨時接入網絡的移動節點組成，節點間通信由無線網絡傳輸完成，不依賴於固定通信網絡基礎設施，具有無中心、自組織、網絡拓撲結構動態變化等特點，在個人區域網、家庭組網、搜索救援行動、商業教育應用和傳感器網絡等領域具有廣闊應用前景。但是，Ad Hoc網絡的靈活性和不依賴基礎設施的特點導致網絡數據包衝突較多，造成網絡吞吐量較低，丟包率較大和時延較長等缺點，這些缺陷可通過改進網絡MAC層協議來緩解。MAC層協議主要解決如何在相互競爭的用戶之間分配無線信道問題，即無線節點如何接入無線信道來發射數據幀。研究人員已經進行了大量研究，提出了種種協議以改善MAC層性能，MAC層協議分為單信道協議和多信道協議兩類。IEEE 802.11是典型的單信道MAC層協議，也是無線區域網的標準(IEEE STD.802.11.Wireless LAN medium access control (MAC) and physical layer (PHY)speci cations.1999)，它釆用CSMA/CA技術避免信道衝突。其他單信道協議還包括基於純競爭方式(Pure Contention-based)的 MACA 協議(P.Karn.MACA - a newchannel access method for packet radi0.1n: Proc.0f the ARRL/CRRL AmateurRadio 9th Computer Networking Conference.1990 (9): 134 140)、基於忙音方式(BusyTone-based)的 PUMA 協議(M.Natkaniecj A.R.Pach.PUMA - a new channel accessprotocol for wireless LANs.1n: Proc.0f the 5th International Symposium onWireless Personal Multimedia Communications.2002:1351 1355)、米用功率控制(Power-aware)的PCM協議(E.S.Jungj Ν.H.Vaidya.A power control MAC protocolfor ad hoc networks.Wireless Networks.2005，11 (I):55 66)、基於定向天線技術(Directional Antenna-based)的DMAC協議(R.R.Choudhuryj X.Yang, R.RamanathanjN.H.Vaidya.Using directional antennas for medium access control in ad hocnetworks.1n: Proc.0f the 8th ACM Annual International Conference on MobileComputing and Networking.2002:59 70)等。單信道協議具有控制方式簡單的特點，但較易造成數據傳輸衝突。但是，當可用信道數目增加時，單信道協議無法充分利用信道資源。多信道協議可以充分利用信道資源，減少衝突，但控制方式需要精心設計。DCA(Dynamic Channel Allocation)協議(S.Wuj C.Linj Y.Tseng, J.Sheu.A NewMult1-Channel MAC Protocol with On Demand Channel Assignment for Mobile Ad-HocNetworks.1nternational Symposium on Parallel Architectures, Algorithms andNetworks.2000(12):232 248)使用一個固定的控制信道傳輸控制分組，其他信道劃分為多個獨立的數據信道傳輸數據分組。HRMA(Hop-Reservation Multiple Access)協議(Tzamaloukas, J.J.Garcia-Luna-Aceves.Channel-Ropping Multiple Access.1n:Proc.1EEE ICC 2000，New Orleans, Louisiana.2000 (8): 18 22)是一種多時隙交互的多信道協議，採用同步技術產生幾個時隙，分別用於RTS分組、CTS分組、DATA分組和ACK分組，從而使RTS不會與CTS衝突，經過RTS和CTS握手確認後的DATA分組和ACK分組也不會衝突。MMAC(Mult1-channel MAC)協議(Jeonghoon Mo, HoiSheung Wilson So, Jeanffalrand.Comparison of Mult1-Channel MAC Protocols for Wireless Networks.ACM/IEEE MSWIM.2005 (10):209 218)使用面向連接的信道分配策略，通過時序表安排或者通過競爭來決定信道歸屬權。McMAC(Multi channel MAC)協議(H.ff.So, J.ffalrand.McMAC: a Mult1-Channel MAC Proposal for Ad-Hoc Wireless Networks.TechnicalReport.2005(4):116 122)同樣使用面向連接的信道分配策略，每個節點選擇一個種子生成一個偽隨機跳躍序列，當節點空閒時，它按照這個預設序列在多個信道上跳躍。以上協議均未考慮鄰居節點將要採取的信道分配策略，因此容易造成衝突。AdHoc網絡節點間的信道分配應由各通信節點對協商完成，為了最大程度滿足自身需求，節點需要考慮鄰居節點的行為策略，節點自身的行為策略也會影響鄰居節點，所有節點的行為策略組合決定了每個節點的最終收益，因此節點間信道分配實際屬於多人決策問題，適宜採用博弈論(game theory)方法來解決。博弈論的應用前提為全部參與者均為理性、貪婪的，均不會選擇嚴格劣戰略，並且都知道其他參與者也是理性的。納什均衡(Nash equilibrium)是博弈的平衡狀態,可通過完全且完美信息動態博弈(dynamic game with perfect and complete information)來實現。I)納什均衡納什均衡是指，在博弈論預測的博弈結果中，為每個參與者選定各自的戰略，該戰略應是針對其他參與者選擇戰略的最優反應。因為沒有參與者願意獨自離棄他所選定的戰略，所以所有參與者選擇戰略的組合最終會達到平衡狀態，稱之為納什均衡，該狀態決定了每個參與者的最終收益。

定義:n個參與者標準式博弈如公式(a)所示:G= {S」 S2，…Sn; U1, U2,…，un}(a)其中Si為參與者i的決策行為Si的集合,Ui為參與者i的收益函數。對每一參與者i，如果戰略組合{<，<,...,<}滿足< 是(或至少不劣於)針對其他η-1個參與者所選戰
略{<,...,『,_..,<}的最優反應戰略，則稱戰略組合{ ...，<}是該博弈的一個納什均衡。即對參與者i的收益函數Ui,有:
_2]U1 (5；,...,Sll,s*,sl,,...,sl)>U1 (s*,...,si,,S1 ,si,,...S )(b)對所有Si中的Si都成立，亦即 < 為式(C)描述最優化問題的解:Ui(<，...,Sl^Si,s*+1,---,s*n)(C)與納什均衡推導密切相關的是協議理念:對給定的博弈，如果參與者之間要商定一個協議來決定博弈如何進行，那麼一個有效協議中的戰略組合必須是納什均衡的戰略組合，否則，至少有一個參與者沒有遵守該協議。2)完全且完美信息動態博弈
完全且完美信息動態博弈是指，在博弈進行的每一步中，參與者都清楚此前博弈進行的整個過程，參與者的行動步驟如下:步驟一:參與者I從可行集S1中選擇一個行動s/ ；步驟二:參與者2觀察到S2'後，從可行集S2中選擇一個行動S2'；步驟三:參與者I和參與者2的收益分別為U1W，s2')和112(8/，s2')。完全且完美信息動態博弈的主要特點有三個:行動是順序發生的；選擇下一步行動之前，所有此前的行動都可被觀察到；在每一種可能的行動組合下，參與者的收益都是共同知識。因此，可以通過逆向歸納法求解此類博弈問題。當在博弈的步驟二，參與者2行動時，由於此前參與者I已選擇行動S1',參與者2面臨的決策問題可用式(d)表示:maxs、m2 ，s2')(d)假定對於51中的每一個s/，參與者2的最優化問題只有惟一解，用R Js/ )表示，即參與者2對參與者I行動的反應，或稱最優反應。由於參與者I與參與者2 —樣,都能夠解出參與者2的問題,且可以預料到參與者2對自己每一個可能行動S1'所做出的反應，因此參與者I在步驟一要解決的問題可歸結為:maxS|,.s, Ii,(.V1',R2(.V1'))(e)假定參與者I的這一最優化問題同樣有惟一解，表示為 <，稱(<，'(.<))為這
一博弈的逆向歸納解。逆向歸納解不含有不可置信的威脅:參與者I預測參與者2將對其可能選擇的任何行動S1做出最優反應，選擇行動R2 (S1);這一預測排除了參與者2不可置信的威脅，即參與者2在步驟二不會做出不符合自身利益的反應。

發明內容
本發明要解決的技術問題是基於博弈論，提出一種Ad Hoc網絡MAC層多信道動態分配方法，本方法的具體實現稱為⑶CA協議(Game based DCA protocol)與傳統的DCA協議和IEEE 802.11協議相比，該協議能夠提高網絡吞吐量、降低丟包率和時延。在Ad Hoc網絡中，參與通信的各節點與其鄰居節點形成一個小區，小區內部節點選擇通信信道時，需考慮通信雙方鄰居節點的當前狀態及其可能的信道選擇方案。由於各節點的通信時機無法預測，因此假定鄰居節點周圍的信道佔用情況反映了該節點加入通信的可能性，即鄰居節點發起通信的概率。在此基礎之上，節點通過逆向歸納計算選擇每條信道的收益，也即有效避免衝突的概率，然後選擇收益最大的信道進行傳輸。小區中各節點狀態最終實現納什均衡，即可得到整體最佳的網絡性能。本發明的具體技術方案如下:在包含η個節點的網絡中，用Ci表示節點i的可選信道集合，其元素為Cij,代表節點i的編號為j的信道。

當節點i選擇數據信道j時，節點i通過逆向歸納預測到其它節點k會據此做出最有利自身通信的信道選擇Rk(Cu)。令節點i的收益函數為Ui,則能夠使Ui取得最大值Uifflax的數據信道j即為節點i的最佳信道，如公式(I)所示:
權利要求
1.種Ad Hoc網絡的MAC層多信道動態分配方法，其特徵在於， 在包含η個節點的網絡中，用Ci表示節點i的可選信道集合，其元素為Cij，代表節點i的編號為j的信道；當節點i選擇數據信道j時，節點i通過逆向歸納預測到其它節點k據此做出最有利自身通信的信道選擇Rk(Cu);令節點i的收益函數為Ui,則能夠使Ui取得最大值Uimax的數據信道j即為節點i的最佳信道，如公式(I)所示:
全文摘要
本發明公開了一種無線MAC層多信道動態分配方法，屬於Ad Hoc網絡領域。多信道Ad Hoc網絡中，參與通信的各節點與其鄰居節點形成一個小區，小區內部節點選擇通信信道時，需考慮通信雙方鄰居節點當前狀態及其可能的信道選擇方案。由於鄰居節點周圍的信道佔用情況可反映該節點加入通信的可能性，即鄰居節點發起通信的概率，因此可通過博弈論的逆向歸納方法計算通信節點選擇每條信道的收益，即有效避免衝突的概率，然後選擇收益最大的信道進行傳輸，直到小區中各節點狀態實現納什均衡，此時網絡達到最佳通信狀態，具有最大的吞吐量、最小的丟包率和時延。本發明的具體實現可作為Ad Hoc網絡節點設備選擇信道的MAC層協議使用。
文檔編號H04W72/04GK103096483SQ201310000568
公開日2013年5月8日 申請日期2013年1月4日 優先權日2013年1月4日
發明者賴曉晨, 王孝良, 韓瑜, 惠煌, 李麗坤, 董書瑾, 李贇, 王克艱, 姚豔雙, 陸思敏, 趙瑩, 周國喬 申請人:大連理工大學