官 錚，胡 揚，楊志軍，何 敏

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

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

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

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

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

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

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

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

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

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

1 系統(tǒng)模型

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

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

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

1.1 全雙工鏈路前提條件

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2 調(diào)度原則

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

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

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

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

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

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

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

對于節(jié)點的所有鄰居節(jié)點N均有：

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

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

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

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

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

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

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

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

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

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

廣播，包含地址。

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

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

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

接收到和后廣播。

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

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

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

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

廣播，包含、、地址。

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

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

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

接收到和后廣播。

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

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

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

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

廣播，包含、地址。

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

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

廣播，包含、、地址。

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

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

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

0接收到和后廣播。

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

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

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

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

廣播，包含、地址。

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

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

廣播，包含、、地址。

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

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

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

0接收到和后廣播。

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

4.1 公平性評價

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

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

對比和，因為中過于頻繁地接入網(wǎng)絡(luò)導(dǎo)致接入網(wǎng)絡(luò)的機(jī)會較少，而中每個節(jié)點接入網(wǎng)絡(luò)機(jī)會相同，所以的節(jié)點接入公平性要好于。采用公平性指標(biāo)：

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

4.2 吞吐量分析

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

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

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

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

4.3 時延分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖8 公平性對比曲線Fig.8 Comparison curve of fairness

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

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

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

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

圖11 平均等待時延對比曲線Fig.11 Comparison curve of average waiting delay

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

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

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

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

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

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

6 結(jié)束語

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

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