分布式WLAN 全雙工鏈路加權(quán)調(diào)度算法

官 錚，胡 揚(yáng)，楊志軍，何 敏

1.云南大學(xué) 信息學(xué)院，昆明650500

2.云南省教育廳 教育科學(xué)研究院，昆明650223

當(dāng)今時(shí)代，隨著新一代信息技術(shù)的發(fā)展和無線接入設(shè)備的普及，移動(dòng)終端的數(shù)量和數(shù)據(jù)都呈現(xiàn)出一個(gè)爆炸式增長(zhǎng)趨勢(shì)，給無線通信網(wǎng)絡(luò)帶來了不小的壓力。當(dāng)前無線局域網(wǎng)絡(luò)大多采用的是半雙工（half-duplex，HD）模式，限制了網(wǎng)絡(luò)性能的同時(shí)也造成了無線頻譜資源的浪費(fèi)。無線網(wǎng)絡(luò)帶內(nèi)全雙工（in-band full-duplex，IBFD）技術(shù)理論上可實(shí)現(xiàn)通信系統(tǒng)信道容量的倍增，近年來隨著自干擾消除（selfinterference cancellation，SIC）等物理層技術(shù)的日漸成熟，通過自干擾抑制和消除技術(shù)，使網(wǎng)絡(luò)中單節(jié)點(diǎn)的同時(shí)同頻全雙工（co-frequency co-time full duplex，CCFD）得以實(shí)現(xiàn)。

然而若要進(jìn)一步實(shí)現(xiàn)多節(jié)點(diǎn)之間的帶內(nèi)全雙工無線通信，一方面，需要抑制節(jié)點(diǎn)間互干擾；另一方面，還需要網(wǎng)絡(luò)層面帶內(nèi)全雙工無線通信MAC 協(xié)議及調(diào)度機(jī)制的支持。

集中式網(wǎng)絡(luò)架構(gòu)WLAN 中，位于基站的接入點(diǎn)（access point，AP）集合了802.11 標(biāo)準(zhǔn)定義的所有功能,無線資源都通過AP 在全網(wǎng)進(jìn)行動(dòng)態(tài)協(xié)調(diào)?，F(xiàn)有大部分IBFD MAC 協(xié)議均針對(duì)集中式網(wǎng)絡(luò)架構(gòu)，即數(shù)據(jù)僅在節(jié)點(diǎn)和AP 之間傳輸，節(jié)點(diǎn)間的數(shù)據(jù)交換需經(jīng)由AP 轉(zhuǎn)發(fā)。針對(duì)節(jié)點(diǎn)間的數(shù)據(jù)傳輸會(huì)在AP 產(chǎn)生碰撞的問題，文獻(xiàn)[5]設(shè)計(jì)出一種全雙工MAC 協(xié)議，發(fā)生碰撞的隱藏節(jié)點(diǎn)通過沖突解碼和報(bào)告（collision decoding and reporting，CDR）匯總給AP，根據(jù)報(bào)告信息再由AP 選擇節(jié)點(diǎn)對(duì)鏈路進(jìn)行調(diào)度以規(guī)避沖突來提升網(wǎng)絡(luò)吞吐量。文獻(xiàn)[6]在IEEE802.11 點(diǎn)協(xié)調(diào)（point coordination function，PCF）機(jī)制的基礎(chǔ)上提出一種用于AP 和站點(diǎn)傳輸?shù)幕旌戏?wù)雙向輪詢?cè)L問控制機(jī)制。以Janus 為代表的預(yù)約式全雙工MAC 協(xié)議通過AP 匯聚節(jié)點(diǎn)信息、維護(hù)上下行調(diào)度順序，節(jié)點(diǎn)在AP 控制下建立全雙工鏈路。

傳統(tǒng)通信能力的增長(zhǎng)嚴(yán)重依賴基礎(chǔ)設(shè)施和資源投入，如從2G到5G，通信效率提升亟待開拓新維度。隨著移動(dòng)通信從3G 頻段提升至高頻毫米波頻段可有效提升帶寬，受高頻信號(hào)傳播范圍小的約束，對(duì)等用戶之間的直接通信，將更利于短距離通信。此外，用戶在訪問硬件資源時(shí)無需借助于其他中間實(shí)體，也可有效提升硬件的訪問速度。

隨著網(wǎng)絡(luò)架構(gòu)逐漸以基站為中心被調(diào)整為以用戶為中心，設(shè)計(jì)分布式IBFD MAC 協(xié)議成為實(shí)現(xiàn)無中心控制下多節(jié)點(diǎn)同時(shí)同頻接入的關(guān)鍵。

目前的分布式無線網(wǎng)絡(luò)中應(yīng)用同時(shí)同頻全雙工的協(xié)議大多是基于IEEE 802.11 協(xié)議中的CSMA/CA機(jī)制?；旌想p工媒體接入控制協(xié)議（hybrid-duplex MAC，HYD-MAC）根據(jù)鏈路調(diào)度時(shí)網(wǎng)絡(luò)節(jié)點(diǎn)狀態(tài)和全雙工能力自適應(yīng)選擇傳輸模式。文獻(xiàn)[14]提出一種將TDMA 和CCFD 相結(jié)合的MAC 協(xié)議，通過建立二級(jí)鏈路來增加同一時(shí)隙中的共存的傳輸鏈路數(shù)以改善重負(fù)載時(shí)網(wǎng)絡(luò)的時(shí)延和吞吐量。趙陽提出一種基于預(yù)約的分布式多信道鏈路調(diào)度算法（based on reservation-distributed multi-channel，BR-DMC），通過預(yù)約的方式分配節(jié)點(diǎn)不同信道上的時(shí)隙資源，能夠無沖突地進(jìn)行鏈路調(diào)度，動(dòng)態(tài)地適應(yīng)業(yè)務(wù)變化，實(shí)現(xiàn)了移動(dòng)自組織網(wǎng)絡(luò)下的分布式獨(dú)立多信道鏈路調(diào)度。但是上述鏈路調(diào)度算法主要是針對(duì)網(wǎng)絡(luò)吞吐量和時(shí)延進(jìn)行優(yōu)化，未考慮節(jié)點(diǎn)公平性和協(xié)議的后向兼容性問題。

傳統(tǒng)的分布式網(wǎng)絡(luò)在進(jìn)行鏈路調(diào)度的節(jié)點(diǎn)選取時(shí)大多采用隨機(jī)接入的方式，這就有可能導(dǎo)致某些數(shù)據(jù)量大的節(jié)點(diǎn)接入網(wǎng)絡(luò)的等待時(shí)間較長(zhǎng)，而其他節(jié)點(diǎn)過于頻繁的工作使得系統(tǒng)在時(shí)間和空間資源利用上不公平。Ad Hoc 網(wǎng)絡(luò)節(jié)點(diǎn)間組成的網(wǎng)絡(luò)具有臨時(shí)性，彼此通信通常要經(jīng)過多跳才能實(shí)現(xiàn)。對(duì)于某些沒有基礎(chǔ)通信設(shè)施環(huán)境，如部隊(duì)的協(xié)同作戰(zhàn)、野外考察、災(zāi)后營(yíng)救等場(chǎng)合，Ad Hoc 網(wǎng)絡(luò)以其靈活的組網(wǎng)方式備受關(guān)注。在這些場(chǎng)合下，除了對(duì)網(wǎng)絡(luò)的傳統(tǒng)數(shù)據(jù)傳輸?shù)闹笜?biāo)進(jìn)行要求外，每個(gè)節(jié)點(diǎn)的反應(yīng)應(yīng)更加迅速，節(jié)點(diǎn)間的數(shù)據(jù)傳輸應(yīng)更加及時(shí)，因此需要考慮分布式場(chǎng)景下節(jié)點(diǎn)的公平性需求。此外，在工業(yè)物聯(lián)網(wǎng)等超可靠、高時(shí)效性網(wǎng)絡(luò)中，除考慮節(jié)點(diǎn)發(fā)送時(shí)延平均性能外，還應(yīng)關(guān)注其尾部特性。

本文提出一種基于節(jié)點(diǎn)調(diào)度權(quán)重的全雙工鏈路調(diào)度算法（full-duplex link scheduling algorithm based on nodal scheduling weights，W-FD），能夠綜合考慮節(jié)點(diǎn)的數(shù)據(jù)收發(fā)能力和鏈路結(jié)構(gòu)對(duì)網(wǎng)絡(luò)中的節(jié)點(diǎn)和調(diào)度過程進(jìn)行動(dòng)態(tài)調(diào)整，在提高吞吐量和降低時(shí)延的同時(shí)有效保障了節(jié)點(diǎn)的公平性需求。

1 系統(tǒng)模型

系統(tǒng)采用分布式網(wǎng)絡(luò)架構(gòu)，無中心控制節(jié)點(diǎn)，數(shù)據(jù)在節(jié)點(diǎn)間轉(zhuǎn)發(fā)，即每個(gè)節(jié)點(diǎn)在網(wǎng)絡(luò)中均可充當(dāng)發(fā)送者、接收者和中繼?？刂撇呗阅Ｐ腿鐖D1 所示。圖中，、為由與節(jié)點(diǎn)發(fā)送和接收相關(guān)的業(yè)務(wù)隊(duì)列、緩沖區(qū)大小和拓?fù)浣Y(jié)構(gòu)等構(gòu)成的函數(shù)；為節(jié)點(diǎn)的調(diào)度權(quán)重；為節(jié)點(diǎn)的全雙工閾值，用于判定優(yōu)先節(jié)點(diǎn)在鏈路中的雙工模式；為節(jié)點(diǎn)的工作狀態(tài)；為傳輸鏈路中的節(jié)點(diǎn)的工作模式；e、e為節(jié)點(diǎn)的權(quán)重修正參數(shù)。

圖1 控制策略模型Fig.1 Model of control strategy

假設(shè)網(wǎng)絡(luò)中所有節(jié)點(diǎn)均有數(shù)據(jù)待發(fā)送，在調(diào)度過程開始前節(jié)點(diǎn)根據(jù)自身的業(yè)務(wù)隊(duì)列、緩沖區(qū)大小和拓?fù)浣Y(jié)構(gòu)等計(jì)算出自身的調(diào)度權(quán)重(=e f+e f)，通過節(jié)點(diǎn)以及其鄰居節(jié)點(diǎn)組成的鄰域內(nèi)調(diào)度權(quán)重的對(duì)比，選取權(quán)值最大(Argmax())的節(jié)點(diǎn)作為優(yōu)先節(jié)點(diǎn)并建立數(shù)據(jù)傳輸鏈路，為了避免產(chǎn)生碰撞，鄰域內(nèi)不參與鏈路傳輸?shù)墓?jié)點(diǎn)應(yīng)根據(jù)其與鏈路的關(guān)系對(duì)自身狀態(tài)重新定義(,)，并將修正參數(shù)反饋給節(jié)點(diǎn)(e,e)，對(duì)自身的調(diào)度權(quán)重進(jìn)行修正。對(duì)于未參與鏈路建立的節(jié)點(diǎn)，其調(diào)度權(quán)重會(huì)隨著時(shí)間增加；而對(duì)于參與鏈路建立的節(jié)點(diǎn)，在下一次調(diào)度開始前，該節(jié)點(diǎn)會(huì)根據(jù)自身工作模式將調(diào)度權(quán)重置0 并重新計(jì)算。

1.1 全雙工鏈路前提條件

（1）全連通分布式網(wǎng)絡(luò)：網(wǎng)絡(luò)中所有節(jié)點(diǎn)與其他任意節(jié)點(diǎn)均有路徑可達(dá)，每個(gè)節(jié)點(diǎn)至少有兩個(gè)鄰居節(jié)點(diǎn)。

（2）同時(shí)同頻全雙工技術(shù)：允許節(jié)點(diǎn)在同一頻段上發(fā)送數(shù)據(jù)的同時(shí)也能夠接收數(shù)據(jù)。

如圖2（a）中、構(gòu)成雙向鏈路，（b）中、、構(gòu)成二級(jí)鏈路。

圖2 全雙工鏈路示意圖Fig.2 Full-duplex links in network

圖2 表示為分布式結(jié)構(gòu)網(wǎng)絡(luò)中的兩種全雙工鏈路。圖2（a）中節(jié)點(diǎn)和同時(shí)處于發(fā)送和接收狀態(tài)，且互為發(fā)送的源節(jié)點(diǎn)和接收的目的節(jié)點(diǎn)，因此和構(gòu)建雙向鏈路；圖2（b）中節(jié)點(diǎn)處于發(fā)送狀態(tài)，處于發(fā)送和接收狀態(tài)，處于接收狀態(tài)，既是的目的節(jié)點(diǎn)又是發(fā)送數(shù)據(jù)至的源節(jié)點(diǎn)，因此、和三個(gè)節(jié)點(diǎn)構(gòu)成二級(jí)鏈路。

1.2 節(jié)點(diǎn)狀態(tài)描述

在基于802.11 協(xié)議的基礎(chǔ)上，本文對(duì)分布式網(wǎng)絡(luò)中的任一節(jié)點(diǎn)的狀態(tài)定義如下：

其中，S=00 表示節(jié)點(diǎn)為自由狀態(tài)，允許接收和發(fā)送數(shù)據(jù)；S=01 表示節(jié)點(diǎn)為接收禁止?fàn)顟B(tài)；S=10表示節(jié)點(diǎn)為發(fā)送禁止?fàn)顟B(tài)；S=11 表示節(jié)點(diǎn)為靜默狀態(tài)，不允許發(fā)送和接收數(shù)據(jù)。

對(duì)于已經(jīng)建立數(shù)據(jù)傳輸鏈路的節(jié)點(diǎn)，對(duì)工作模式的定義如下：

其中，SL=00 表示節(jié)點(diǎn)處于全雙工模式；SL=01表示節(jié)點(diǎn)處于半雙工中的發(fā)送模式；SL=10 表示節(jié)點(diǎn)處于半雙工中的接收模式。

對(duì)于鏈路中節(jié)點(diǎn)的鏈路外鄰居節(jié)點(diǎn)，為了消除對(duì)數(shù)據(jù)傳輸鏈路的干擾，其節(jié)點(diǎn)狀態(tài)會(huì)受到鏈路影響。對(duì)不同工作模式下的節(jié)點(diǎn)，其鏈路外的鄰居節(jié)點(diǎn)狀態(tài)如圖3 所示。

圖3 鏈路外的鄰居節(jié)點(diǎn)狀態(tài)Fig.3 Status of neighbor node outside transmission link

圖3 所示為鏈路外鄰居節(jié)點(diǎn)，（a）中節(jié)點(diǎn)處于發(fā)送狀態(tài)，為了避免受到來自節(jié)點(diǎn)發(fā)送數(shù)據(jù)的干擾，節(jié)點(diǎn)應(yīng)為禁止接收狀態(tài)；同理，（b）中節(jié)點(diǎn)處于接收狀態(tài)，為了確保成功接收，節(jié)點(diǎn)應(yīng)為禁止發(fā)送狀態(tài)；（c）中同時(shí)處于發(fā)送和接收狀態(tài)，此時(shí)只能處于靜默狀態(tài)。

2 加權(quán)式全雙工鏈路調(diào)度算法

為了在優(yōu)化節(jié)點(diǎn)吞吐量和降低時(shí)延的同時(shí)提高節(jié)點(diǎn)的公平性，本文提出一種基于節(jié)點(diǎn)調(diào)度權(quán)重的鏈路調(diào)度算法。假設(shè)全聯(lián)通分布式網(wǎng)絡(luò)中所有節(jié)點(diǎn)均具有全雙工能力，信息分組在產(chǎn)生和傳輸?shù)倪^程中無丟包等情況。在鏈路建立前各個(gè)節(jié)點(diǎn)為自身分配權(quán)值，分布式網(wǎng)絡(luò)中多節(jié)點(diǎn)滿足鏈路建立條件時(shí)，根據(jù)調(diào)度權(quán)重決定的節(jié)點(diǎn)接入優(yōu)先級(jí)和鏈路類型選取鏈路建立對(duì)象，權(quán)重值越高的節(jié)點(diǎn)參與鏈路傳輸?shù)臋C(jī)會(huì)越大，從而在實(shí)現(xiàn)全雙工鏈路調(diào)度的同時(shí)保證了節(jié)點(diǎn)公平性。

2.1 節(jié)點(diǎn)調(diào)度權(quán)重

節(jié)點(diǎn)調(diào)度權(quán)重由以下三個(gè)因素決定：

（1）個(gè)體因素：節(jié)點(diǎn)自身的收發(fā)能力、拓?fù)浣Y(jié)構(gòu)。

（2）環(huán)境因素：所有鄰居節(jié)點(diǎn)的收發(fā)能力、拓?fù)浣Y(jié)構(gòu)。

（3）時(shí)間因素：節(jié)點(diǎn)接入鏈路的時(shí)間間隔、鏈路的調(diào)度間隔。

設(shè)節(jié)點(diǎn)等待發(fā)送的業(yè)務(wù)數(shù)為m，節(jié)點(diǎn)允許緩存的最大業(yè)務(wù)量為，鄰居節(jié)點(diǎn)個(gè)數(shù)為n，其集合為N，節(jié)點(diǎn)作為發(fā)送節(jié)點(diǎn)的間隔時(shí)間為t,節(jié)點(diǎn)作為接收節(jié)點(diǎn)的間隔時(shí)間為t。假設(shè)b∈N(1 ≤≤n)，鏈路(,b)的調(diào)度間隔為t。 e和e表示節(jié)點(diǎn)的權(quán)重修正參數(shù)。定義E為節(jié)點(diǎn)的發(fā)送能力，E為節(jié)點(diǎn)的接收能力，B表示節(jié)點(diǎn)的發(fā)送系數(shù)，B表示節(jié)點(diǎn)的接收系數(shù)，根據(jù)式（3）～（6）計(jì)算。

式中，K表示節(jié)點(diǎn)自影響發(fā)送權(quán)重參數(shù)，K表示節(jié)點(diǎn)與鄰居間互影響發(fā)送權(quán)重參數(shù)，定義如下：

式中，e表示節(jié)點(diǎn)是否被允許發(fā)送，允許時(shí)e=1，禁止時(shí)e=0。

K表示節(jié)點(diǎn)自影響接收權(quán)重參數(shù)，K表示節(jié)點(diǎn)與鄰居間互影響接收權(quán)重參數(shù)，定義如下：

W表示節(jié)點(diǎn)的接收權(quán)重：

式中，e表示節(jié)點(diǎn)是否被允許接收，允許時(shí)e=1，禁止時(shí)e=0。

式（3）和式（4）是對(duì)節(jié)點(diǎn)自身收發(fā)能力的定義，若等待發(fā)送的業(yè)務(wù)數(shù)m越大，則節(jié)點(diǎn)在后續(xù)的調(diào)度過程中作為發(fā)送節(jié)點(diǎn)接入網(wǎng)絡(luò)的機(jī)會(huì)越多，表明發(fā)送能力E越大；若m越小，則節(jié)點(diǎn)業(yè)務(wù)緩存隊(duì)列的空位越多，在后續(xù)的調(diào)度過程中作為接收和中繼轉(zhuǎn)發(fā)節(jié)點(diǎn)接入網(wǎng)絡(luò)的機(jī)會(huì)越多，表明接收能力E越大。式（5）和式（6）是出于對(duì)節(jié)點(diǎn)接入優(yōu)先級(jí)的考慮，節(jié)點(diǎn)在選擇鄰居節(jié)點(diǎn)作為鏈路建立對(duì)象時(shí)，除目的節(jié)點(diǎn)以外的其他鄰居節(jié)點(diǎn)都會(huì)受到限制，因此，節(jié)點(diǎn)的n越大則接入網(wǎng)絡(luò)時(shí)受到限制的鄰居節(jié)點(diǎn)越多，優(yōu)先順序應(yīng)當(dāng)靠后；節(jié)點(diǎn)及其鄰居節(jié)點(diǎn)的業(yè)務(wù)隊(duì)列會(huì)隨時(shí)間累加，而t和t作為節(jié)點(diǎn)發(fā)送和接收的響應(yīng)等待時(shí)間，考慮節(jié)點(diǎn)自身的負(fù)載均衡，t和t越大則節(jié)點(diǎn)的優(yōu)先級(jí)越高。式（7）和式（10）是對(duì)發(fā)送自影響參數(shù)和接收自影響參數(shù)的定義，在式（5）和式（6）的基礎(chǔ)上，加入了對(duì)節(jié)點(diǎn)與所有鄰居節(jié)點(diǎn)建立鏈路的調(diào)度間隔的考慮，作為對(duì)節(jié)點(diǎn)所在鄰域在時(shí)間因素下對(duì)整個(gè)網(wǎng)絡(luò)影響的一個(gè)補(bǔ)正。

與上述同理，式（10）～（12）用于計(jì)算與節(jié)點(diǎn)的接收權(quán)重W和與之相關(guān)的參數(shù)。

W和W分別被定義為綜合考慮個(gè)體、環(huán)境和時(shí)間因素下節(jié)點(diǎn)作為發(fā)送和接收節(jié)點(diǎn)的可能性，在下文中，W和W的作用體現(xiàn)在：（1）計(jì)算節(jié)點(diǎn)的調(diào)度總權(quán)重W，W與其所有鄰居節(jié)點(diǎn)的W的比較用于定義優(yōu)先節(jié)點(diǎn)；（2）若節(jié)點(diǎn)為優(yōu)先節(jié)點(diǎn)，根據(jù)W和W的比較來判定節(jié)點(diǎn)的雙工模式；（3）若節(jié)點(diǎn)不為優(yōu)先節(jié)點(diǎn)，則W和W用于與非優(yōu)先節(jié)點(diǎn)的其他節(jié)點(diǎn)競(jìng)爭(zhēng)，由優(yōu)先節(jié)點(diǎn)來判斷節(jié)點(diǎn)能否成為建立鏈路的目的節(jié)點(diǎn)。

式（13）表示節(jié)點(diǎn)在不同狀態(tài)下e和e的取值。

式（14）的W表示節(jié)點(diǎn)的調(diào)度總權(quán)重：

（優(yōu)先節(jié)點(diǎn)）對(duì)于節(jié)點(diǎn)以及其任意鄰居節(jié)點(diǎn)b∈N，若調(diào)度總權(quán)重滿足

則節(jié)點(diǎn)為優(yōu)先節(jié)點(diǎn)。時(shí)隙中的優(yōu)先節(jié)點(diǎn)具有較高的機(jī)會(huì)參與鏈路調(diào)度。

2.2 調(diào)度原則

根據(jù)定義1 可得出下述定理1：

在一個(gè)由全向傳輸?shù)娜p工節(jié)點(diǎn)組成的網(wǎng)絡(luò)中，同一時(shí)隙中任意兩個(gè)優(yōu)先節(jié)點(diǎn)的最短跳數(shù)至少為2。

設(shè)網(wǎng)絡(luò)中兩個(gè)節(jié)點(diǎn)、，其鄰居節(jié)點(diǎn)集合分別為N、N，對(duì)于任意節(jié)點(diǎn)∈N，∈N均有W＞W，W＞W，則節(jié)點(diǎn)、為優(yōu)先節(jié)點(diǎn)且≠，≠。若、最短跳數(shù)為1，則∈N，∈N，與≠，≠矛盾，故節(jié)點(diǎn)、之間最短跳數(shù)至少為2。

上述定理保證了優(yōu)先節(jié)點(diǎn)之間的發(fā)送和接收互不干擾。

2.3 優(yōu)先節(jié)點(diǎn)的雙工模式

為了對(duì)優(yōu)先節(jié)點(diǎn)工作的雙工模式進(jìn)行判定，提出節(jié)點(diǎn)全雙工閾值的概念。

假設(shè)節(jié)點(diǎn)為優(yōu)先節(jié)點(diǎn)，當(dāng)節(jié)點(diǎn)數(shù)據(jù)收發(fā)能力滿足以下關(guān)系時(shí)：

對(duì)于節(jié)點(diǎn)的所有鄰居節(jié)點(diǎn)N均有：

此時(shí)節(jié)點(diǎn)所有鄰居節(jié)點(diǎn)均具有雙向傳輸?shù)淖畲罂赡苄?。?jù)此定義節(jié)點(diǎn)的全雙工閾值ε：

（1）W≠0，W≠0，若 |W-W|≤ε，則SL=00，節(jié)點(diǎn)工作在全雙工模式下；若W-W＞ε，則SL=01，節(jié)點(diǎn)工作在發(fā)送模式下；若W-W＜ε，則SL=10，節(jié)點(diǎn)工作在接收模式下。

（2）W≠0，W=0，則SL=01，節(jié)點(diǎn)工作在發(fā)送模式下。

（3）W=0，W≠0，則SL=10，節(jié)點(diǎn)工作在接收模式下。

3 鏈路調(diào)度過程

在鏈路調(diào)度開始前，所有節(jié)點(diǎn)需要對(duì)各自的鄰居節(jié)點(diǎn)廣播自身的B、B值，以獲得節(jié)點(diǎn)與其鄰居節(jié)點(diǎn)的調(diào)度權(quán)重。節(jié)點(diǎn)答復(fù)請(qǐng)求過程遵循CSMA/CA 工作機(jī)制。根據(jù)優(yōu)先節(jié)點(diǎn)的工作模式的不同，鏈路的調(diào)度類型也有所不同。

（1）優(yōu)先節(jié)點(diǎn)工作在全雙工模式下的雙向鏈路。如圖4 所示，節(jié)點(diǎn)、分別是節(jié)點(diǎn)、的鄰居節(jié)點(diǎn)，優(yōu)先節(jié)點(diǎn)根據(jù)業(yè)務(wù)需求和調(diào)度權(quán)重選擇節(jié)點(diǎn)作為建立全雙工雙向鏈路的目的節(jié)點(diǎn)，構(gòu)建鏈路?(SL=SL=00)。為了避免對(duì)鏈路?的干擾，作為鄰居節(jié)點(diǎn)的、此時(shí)應(yīng)滿足S=S=11，于是e=e=e=e=0，因此在修正和廣播自身權(quán)重后，節(jié)點(diǎn)、應(yīng)保持靜默直到?傳輸過程結(jié)束。

圖4 雙向鏈路調(diào)度過程Fig.4 Scheduling process of bidirectional link

廣播，詢問鄰點(diǎn)業(yè)務(wù)需求，有需求的鄰點(diǎn)答復(fù)W、W。

得出max(W)、max(W)對(duì)應(yīng)相同地址（節(jié)點(diǎn)）。

廣播，包含地址。

答復(fù)并廣播，短幀間隔后廣播。

所有接收到、、的節(jié)點(diǎn)修正自身調(diào)度權(quán)重值并廣播。

鄰點(diǎn)除外，接收到后禁止發(fā)送數(shù)據(jù)，接收到后禁止接收數(shù)據(jù)。鄰點(diǎn)除外，接收到后保持靜默。

接收到和后廣播。

（2）優(yōu)先節(jié)點(diǎn)工作在全雙工模式下的二級(jí)鏈路。如圖5 所示，節(jié)點(diǎn)、、分別是節(jié)點(diǎn)、、的鄰居節(jié)點(diǎn)，優(yōu)先節(jié)點(diǎn)根據(jù)業(yè)務(wù)需求和調(diào)度權(quán)重分別選擇節(jié)點(diǎn)、作為建立全雙工二級(jí)鏈路中的上游節(jié)點(diǎn)和下游節(jié)點(diǎn)，構(gòu)建鏈路→→(SL=01,SL=00,SL=10),于是e=0，e=e=0，e=0，因此在修正和廣播自身權(quán)重后節(jié)點(diǎn)應(yīng)保持禁止接收狀態(tài)，節(jié)點(diǎn)應(yīng)保持靜默狀態(tài)，節(jié)點(diǎn)應(yīng)保持禁止發(fā)送狀態(tài)直到→→傳輸過程結(jié)束。

圖5 全雙工模式下優(yōu)先節(jié)點(diǎn)的二級(jí)鏈路調(diào)度過程Fig.5 Scheduling process of secondary link by full-duplex priority node

廣播，詢問鄰點(diǎn)業(yè)務(wù)需求，有需求的鄰點(diǎn)答復(fù)W、W。

得出max(W)、max(W)以及對(duì)應(yīng)的地址（節(jié)點(diǎn)、）。

廣播，包含、、地址。

答復(fù)并廣播，答復(fù)并廣播。和均包含地址。

所有接收到、、的節(jié)點(diǎn)修正自身調(diào)度權(quán)重值并廣播。

鄰點(diǎn)除外，接收到后禁止接收數(shù)據(jù)；鄰點(diǎn)除外，接收到后禁止發(fā)送數(shù)據(jù)；鄰點(diǎn)除、外，接收到后保持靜默。

接收到和后廣播。

（3）優(yōu)先節(jié)點(diǎn)工作在發(fā)送模式下的二級(jí)鏈路。如圖6 所示，節(jié)點(diǎn)、、分別是節(jié)點(diǎn)、、的鄰居節(jié)點(diǎn)，優(yōu)先節(jié)點(diǎn)根據(jù)業(yè)務(wù)需求和調(diào)度權(quán)重選擇節(jié)點(diǎn)作為建立全雙工二級(jí)鏈路中的中繼節(jié)點(diǎn)，節(jié)點(diǎn)再根據(jù)業(yè)務(wù)需求和調(diào)度權(quán)重選擇節(jié)點(diǎn)作為下游節(jié)點(diǎn)，構(gòu)建鏈路→→(SL=01,SL=00,SL=10)，于是e=0，e=e=0，e=0，因此在修正和廣播自身權(quán)重后節(jié)點(diǎn)應(yīng)保持禁止接收狀態(tài)，節(jié)點(diǎn)應(yīng)保持靜默狀態(tài)，節(jié)點(diǎn)應(yīng)保持禁止發(fā)送狀態(tài)直到→→傳輸過程結(jié)束。

圖6 發(fā)送模式下優(yōu)先節(jié)點(diǎn)的二級(jí)鏈路調(diào)度過程Fig.6 Scheduling process of secondary link by sending priority node

廣播，詢問有業(yè)務(wù)需求鄰點(diǎn)的W，鄰點(diǎn)答復(fù)。

得出max(W)以及對(duì)應(yīng)的地址（節(jié)點(diǎn)）。

廣播，包含、地址。

接收到后廣播，詢問除外有業(yè)務(wù)需求鄰點(diǎn)的W，鄰點(diǎn)答復(fù)。

得出max(W)以及對(duì)應(yīng)的地址（節(jié)點(diǎn)）。

廣播，包含、、地址。

答復(fù)并廣播，答復(fù)并廣播。和均包含地址。

所有接收到、、的節(jié)點(diǎn)修正自身調(diào)度權(quán)重值并廣播。

鄰點(diǎn)除外，接收到后禁止接收數(shù)據(jù)；鄰點(diǎn)除外，接收到后禁止發(fā)送數(shù)據(jù)；鄰點(diǎn)除、外，接收到后保持靜默。

0接收到和后廣播。

（4）優(yōu)先節(jié)點(diǎn)工作在接收模式下的二級(jí)鏈路。如圖7 所示，節(jié)點(diǎn)、、分別是節(jié)點(diǎn)、、的鄰居節(jié)點(diǎn)，優(yōu)先節(jié)點(diǎn)根據(jù)業(yè)務(wù)需求和調(diào)度權(quán)重選擇節(jié)點(diǎn)作為建立全雙工二級(jí)鏈路中的中繼節(jié)點(diǎn)，節(jié)點(diǎn)再根據(jù)業(yè)務(wù)需求和調(diào)度權(quán)重選擇節(jié)點(diǎn)作為上游節(jié)點(diǎn)，構(gòu)建鏈路→→(SL=01,SL=00,SL=10)，于是e=0，e=e=0，e=0，因此在修正和廣播自身權(quán)重后節(jié)點(diǎn)應(yīng)保持禁止接收狀態(tài)，節(jié)點(diǎn)應(yīng)保持靜默狀態(tài)，節(jié)點(diǎn)應(yīng)保持禁止發(fā)送狀態(tài)直到→→傳輸過程結(jié)束。

圖7 接收模式下優(yōu)先節(jié)點(diǎn)的二級(jí)鏈路調(diào)度過程Fig.7 Scheduling process of secondary link by receiving priority node

廣播，詢問有業(yè)務(wù)需求鄰點(diǎn)的W，鄰點(diǎn)答復(fù)。

得出max(W)以及對(duì)應(yīng)的地址（節(jié)點(diǎn)）。

廣播，包含、地址。

接收到后廣播，詢問除外有業(yè)務(wù)需求鄰點(diǎn)的W，鄰點(diǎn)答復(fù)。

得出max(W)以及對(duì)應(yīng)的地址（節(jié)點(diǎn)）。

廣播，包含、、地址。

答復(fù)并廣播，答復(fù)并廣播。和均包含地址。

所有接收到、、的節(jié)點(diǎn)修正自身調(diào)度權(quán)重值并廣播。

鄰點(diǎn)除外，接收到后禁止發(fā)送數(shù)據(jù)；鄰點(diǎn)除外，接收到后禁止接收數(shù)據(jù)；鄰點(diǎn)除、外，接收到后保持靜默。

0接收到和后廣播。

4 算法性能指標(biāo)

4.1 公平性評(píng)價(jià)

傳統(tǒng)MAC 協(xié)議中節(jié)點(diǎn)參與網(wǎng)絡(luò)以隨機(jī)接入的方式實(shí)現(xiàn)，成功發(fā)送數(shù)據(jù)的節(jié)點(diǎn)總是可以得到更多的信道占用機(jī)會(huì)，而失敗的節(jié)點(diǎn)一直處于忙等狀態(tài)，導(dǎo)致現(xiàn)實(shí)中有些節(jié)點(diǎn)會(huì)因?yàn)槠渌?jié)點(diǎn)的惡意破壞而失去發(fā)送機(jī)會(huì)。

假設(shè)節(jié)點(diǎn)、和互為鄰居節(jié)點(diǎn)，在不考慮節(jié)點(diǎn)待發(fā)業(yè)務(wù)的情況下，在傳統(tǒng)MAC 協(xié)議中，假設(shè)網(wǎng)絡(luò)接入周期為，節(jié)點(diǎn)、和接入網(wǎng)絡(luò)的次序的可能情況是：

對(duì)比和，因?yàn)橹羞^于頻繁地接入網(wǎng)絡(luò)導(dǎo)致接入網(wǎng)絡(luò)的機(jī)會(huì)較少，而中每個(gè)節(jié)點(diǎn)接入網(wǎng)絡(luò)機(jī)會(huì)相同，所以的節(jié)點(diǎn)接入公平性要好于。采用公平性指標(biāo)：

式中，越小，說明節(jié)點(diǎn)的接入公平性越好。而Var=9.92，Var=0，說明的節(jié)點(diǎn)接入公平性達(dá)到最佳狀態(tài)。

4.2 吞吐量分析

為了對(duì)網(wǎng)絡(luò)吞吐量進(jìn)行理論分析，文獻(xiàn)[14]提出了全雙工鏈路網(wǎng)絡(luò)吞吐量概念，假設(shè)節(jié)點(diǎn)分組到達(dá)流滿足均值為的泊松過程，每次發(fā)送一個(gè)數(shù)據(jù)分組且隊(duì)列總不為空。理論上某一時(shí)隙內(nèi)系統(tǒng)的最大網(wǎng)絡(luò)吞吐量如式（18）所示：

其中，P表示系統(tǒng)的最大網(wǎng)絡(luò)吞吐量，表示網(wǎng)絡(luò)的信道容量，表示接入網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)，τ表示同步時(shí)隙長(zhǎng)度，τ表示業(yè)務(wù)時(shí)隙長(zhǎng)度，τ+mτ表示時(shí)隙的總長(zhǎng)度，·τ(0 ＜＜1)表示一個(gè)數(shù)據(jù)分組占用的時(shí)隙長(zhǎng)度，(0 ＜≤1)表示二級(jí)和雙向鏈路的調(diào)度成功率。據(jù)此可知網(wǎng)絡(luò)吞吐量與時(shí)隙內(nèi)共存鏈路數(shù)(,)成正比。

對(duì)于無次級(jí)鏈路調(diào)度的半雙工系統(tǒng)，其最大吞吐量如式（19）所示：

對(duì)比式（18）和式（19）可知，相較于半雙工鏈路調(diào)度，全雙工系統(tǒng)理論上可實(shí)現(xiàn)最大吞吐量的翻倍。

4.3 時(shí)延分析

當(dāng)半雙工系統(tǒng)滿足以下條件時(shí)：

（1）分布式網(wǎng)絡(luò)中所有節(jié)點(diǎn)可被分為個(gè)不重疊的子網(wǎng)絡(luò)；

（2）各子網(wǎng)包含節(jié)點(diǎn)數(shù)大于2 且均為完全圖；

（3）所有節(jié)點(diǎn)的接入公平性達(dá)到最佳狀態(tài)；

（4）各子網(wǎng)中鏈路之間無干擾。

可采用輪詢系統(tǒng)中限定1 服務(wù)模型對(duì)每個(gè)子網(wǎng)絡(luò)的平均等待時(shí)延進(jìn)行推導(dǎo)。

文獻(xiàn)[16]對(duì)限定1 服務(wù)模型的平均等待時(shí)延進(jìn)行了理論推導(dǎo)，假設(shè)系統(tǒng)工作條件如下：

（4）第個(gè)子網(wǎng)中包含節(jié)點(diǎn)數(shù)為N(N＞2)，且各節(jié)點(diǎn)緩存足夠大，不會(huì)產(chǎn)生丟包現(xiàn)象。

在Nδ(θ+γ)＜1 的條件下系統(tǒng)的概率分布達(dá)到穩(wěn)態(tài)，則第個(gè)子網(wǎng)中的信息分組的平均等待時(shí)延為：

據(jù)此可得出整個(gè)半雙工系統(tǒng)的平均等待時(shí)延為：

對(duì)于包含全雙工節(jié)點(diǎn)的系統(tǒng)，信息分組的平均等待時(shí)延為：

5 仿真與結(jié)果分析

本文采用Matlab 仿真工具對(duì)所提出協(xié)議的性能進(jìn)行分析，并和傳統(tǒng)半雙工（RTS/CTS）、FD-TDMA以及ContraFlow 協(xié)議在網(wǎng)絡(luò)吞吐量、時(shí)延、公平性和鏈路調(diào)度間隔方面進(jìn)行實(shí)驗(yàn)對(duì)比。

在一次實(shí)驗(yàn)中，100 m×100 m的區(qū)域內(nèi)隨機(jī)分布著20個(gè)通信節(jié)點(diǎn)，節(jié)點(diǎn)的最大通信距離為35 m，每個(gè)節(jié)點(diǎn)至少有兩個(gè)鄰居節(jié)點(diǎn)，其他仿真參數(shù)均參照文獻(xiàn)[14]設(shè)置，如表1 所示。文中所使用的曲線圖中的每個(gè)樣點(diǎn)圖均來自10 次實(shí)驗(yàn)的平均值。

表1 仿真參數(shù)表Table 1 Simulation parameter table

圖8～圖11 給出了在所有節(jié)點(diǎn)業(yè)務(wù)負(fù)載相同的情況 下，W-FD、傳 統(tǒng)HD（RTS/CTS）、FD-TDMA 和ContraFlow 公平性、鏈路調(diào)度間隔、吞吐量和平均時(shí)延隨信息分組到達(dá)率變化的曲線圖。

圖8 公平性對(duì)比曲線Fig.8 Comparison curve of fairness

圖8 表示W(wǎng)-FD、HD（RTS/CTS）、FD-TDMA 和ContraFlow 的節(jié)點(diǎn)公平性對(duì)比，在信息分組到達(dá)速率較小時(shí)，此時(shí)服務(wù)速率要遠(yuǎn)大于分組到達(dá)率，導(dǎo)致四者方差近似一致，公平性對(duì)比不明顯。但隨著到達(dá)率的提高，圖中HD（RTS/CTS）、FD-TDMA 和Contra-Flow 的方差曲線呈明顯上升趨勢(shì)，而W-FD 算法的方差趨勢(shì)較為平穩(wěn)，說明W-FD 相比HD、FD-TDMA 和ContraFlow 協(xié)議具有更好的節(jié)點(diǎn)公平性。圖9 表示四種協(xié)議鏈路調(diào)度間隔時(shí)間的對(duì)比，圖中每個(gè)采樣點(diǎn)代表網(wǎng)絡(luò)中任意兩個(gè)鄰居節(jié)點(diǎn)所在鏈路的響應(yīng)等待間隔時(shí)間的均值。結(jié)果表明W-FD 的平均鏈路調(diào)度間隔總體上也小于另外三種協(xié)議。

圖9 鏈路調(diào)度間隔對(duì)比曲線Fig.9 Comparison curve of link scheduling interval

采用單位時(shí)隙內(nèi)共存鏈路數(shù)量對(duì)吞吐量進(jìn)行定性分析。如圖10 和圖11 所示，隨著分組到達(dá)率的增加，單位時(shí)隙內(nèi)網(wǎng)絡(luò)中的共存鏈路數(shù)（吞吐量）也隨之增加。傳統(tǒng)RTS/CTS 半雙工鏈路調(diào)度算法在到達(dá)率約為50 分組/s 時(shí)共存鏈路數(shù)達(dá)到飽和，而本文提出的W-FD 在到達(dá)率約為100 分組/s 時(shí)吞吐量才達(dá)到飽和，且比傳統(tǒng)半雙工鏈路調(diào)度算法的最大吞吐量有明顯提高，排隊(duì)時(shí)延有明顯降低。相比于Contra-Flow 協(xié)議，W-FD 在吞吐量和時(shí)延上略有優(yōu)勢(shì)，但與FD-TDMA 相比，在分組到達(dá)率較小時(shí)，W-FD 和FDTDMA 吞吐量和時(shí)延性能雖然相差無幾，但隨著到達(dá)率的增加，F(xiàn)D-TDMA 吞吐量和時(shí)延性能要逐漸優(yōu)于W-FD。這是因?yàn)閃-FD 采用競(jìng)爭(zhēng)接入方式，在高負(fù)載時(shí)，碰撞概率的升高影響了吞吐量和時(shí)延性能的提升。

圖10 時(shí)隙中共存鏈路數(shù)對(duì)比曲線Fig.10 Comparison curve of quantity of co-existing links in slot time

圖11 平均等待時(shí)延對(duì)比曲線Fig.11 Comparison curve of average waiting delay

表2～表4 給出了各節(jié)點(diǎn)到達(dá)率在[1 ,10]、[1 1,50]和[5 1,100] 三個(gè)區(qū)間內(nèi)隨機(jī)取值的情況下，當(dāng)節(jié)點(diǎn)數(shù)分別為20、50 和100 時(shí)W-FD、FD-TDMA 和Contra-Flow 的平均單位時(shí)隙內(nèi)共存鏈路數(shù)、平均等待時(shí)延、節(jié)點(diǎn)休眠時(shí)間方差和平均鏈路調(diào)度間隔。其中每個(gè)數(shù)值均取自10 次實(shí)驗(yàn)平均值。

表2 節(jié)點(diǎn)數(shù)為20 時(shí)三種協(xié)議性能對(duì)比Table 2 Performance comparison of three protocols with 20 nodes

表3 節(jié)點(diǎn)數(shù)為50 時(shí)三種協(xié)議性能對(duì)比Table 3 Performance comparison of three protocols with 50 nodes

表4 節(jié)點(diǎn)數(shù)為100 時(shí)三種協(xié)議性能對(duì)比Table 4 Performance comparison of three protocols with 100 nodes

從表2～表4 可以得知，當(dāng)各節(jié)點(diǎn)擁有不同的分組到達(dá)率時(shí)，隨著節(jié)點(diǎn)數(shù)的增加，F(xiàn)D-TDMA 和Contra-Flow 的節(jié)點(diǎn)休眠時(shí)間方差增幅明顯，而W-FD 算法依舊處于較低值。同時(shí)W-FD 算法下的平均鏈路調(diào)度間隔總體上也小于另外兩者，這表明在分組到達(dá)不對(duì)稱的多節(jié)點(diǎn)環(huán)境下，W-FD 具有更好的節(jié)點(diǎn)接入公平性。此外W-FD 的網(wǎng)絡(luò)吞吐量和時(shí)延性能會(huì)隨著節(jié)點(diǎn)數(shù)的增加而逐漸接近FD-TDMA 和ContraFlow。

實(shí)驗(yàn)表明，在所有節(jié)點(diǎn)擁有相同分組到達(dá)率的較少節(jié)點(diǎn)數(shù)的分布式網(wǎng)絡(luò)中，隨著到達(dá)率的增加，WFD 與FD-TDMA、ContraFlow 相比，雖然吞吐量和時(shí)延性能遜色于另外兩者，但是能夠體現(xiàn)出較好的節(jié)點(diǎn)接入公平性，而且降低了網(wǎng)絡(luò)中的最大時(shí)延，改進(jìn)時(shí)延尾部特性。另外在信息分組到達(dá)不對(duì)稱的多節(jié)點(diǎn)網(wǎng)絡(luò)中，隨著節(jié)點(diǎn)數(shù)的增加，一定區(qū)域內(nèi)網(wǎng)絡(luò)中節(jié)點(diǎn)對(duì)數(shù)也隨之增加，導(dǎo)致通信狀況愈加復(fù)雜。在這種條件下，和FD-TDMA、ContraFlow 相比，W-FD 的吞吐量和時(shí)延能夠得到有效保證，同時(shí)節(jié)點(diǎn)接入公平性更加得到突出。

6 結(jié)束語

為了實(shí)現(xiàn)分布式全雙工鏈路在提高吞吐量和降低時(shí)延的同時(shí)保證節(jié)點(diǎn)接入的最大公平性，提出了一種綜合考慮網(wǎng)絡(luò)吞吐量、時(shí)延、節(jié)點(diǎn)公平性和調(diào)度間隔的分布式全雙工鏈路調(diào)度算法W-FD，先對(duì)節(jié)點(diǎn)的調(diào)度權(quán)重進(jìn)行了定義，再依據(jù)調(diào)度權(quán)重對(duì)鏈路進(jìn)行調(diào)度。實(shí)驗(yàn)結(jié)果表明，W-FD 算法相比傳統(tǒng)半雙工鏈路調(diào)度在改善吞吐量和時(shí)延性能的同時(shí)具有較好的節(jié)點(diǎn)接入公平性，且W-FD在多節(jié)點(diǎn)環(huán)境下相比其他全雙工鏈路調(diào)度算法在節(jié)點(diǎn)接入公平性方面更具備優(yōu)勢(shì)。

本文算法僅針對(duì)在非動(dòng)態(tài)WLAN 結(jié)構(gòu)下節(jié)點(diǎn)的接入，未曾考慮節(jié)點(diǎn)移動(dòng)導(dǎo)致的鏈路中斷等問題；此外，本文算法只對(duì)鄰域內(nèi)鏈路調(diào)度的過程進(jìn)行了優(yōu)化，在考慮整體數(shù)據(jù)傳輸最優(yōu)路徑的情況下還有更深的研究空間。