李建強，張大龍，宋 楊，侯維巖*

(1. 鄭州大學(xué) 信息工程學(xué)院，河南 鄭州 450001；2. 上海大學(xué) 機械自動化學(xué)院，上海 200072)

在分布式無線網(wǎng)絡(luò)低時延、高可靠的應(yīng)用場景中，傳統(tǒng)的路由協(xié)議很難在傳輸時延和開銷均最小時，保證網(wǎng)絡(luò)控制命令的發(fā)送[1].采用可靠單播方式發(fā)送控制命令，可保證傳輸可靠性，但傳輸時延和開銷難以滿足業(yè)務(wù)需求.采用廣播方式發(fā)送控制命令，傳輸時延和開銷較小，但傳輸可靠性難以保證.現(xiàn)有控制命令，由于其分組長度通常較小，多采用廣播方式傳輸.在低時延、高可靠場景中，如無人機群組控制命令的發(fā)送，其發(fā)送速度快、節(jié)點密度高、拓?fù)浣Y(jié)構(gòu)變化快，廣播沖突嚴(yán)重，業(yè)務(wù)成功率較低，傳輸可靠性難以保證.如果加入確認(rèn)機制，由于廣播業(yè)務(wù)的開放性，廣播確認(rèn)開銷隨節(jié)點數(shù)增加呈指數(shù)增長[2].目前，除了常見的基于載波偵聽的洪泛廣播方式外，還沒有一種專門針對低時延、高可靠應(yīng)用場景的高效廣播機制.全網(wǎng)廣播協(xié)議可分為洪泛、概率轉(zhuǎn)發(fā)、骨干轉(zhuǎn)發(fā)3類[3].洪泛廣播冗余轉(zhuǎn)發(fā)次數(shù)多，易致廣播風(fēng)暴，其效率低、時延長[4].概率轉(zhuǎn)發(fā)為每個節(jié)點分配參與轉(zhuǎn)發(fā)的概率，能有效減少廣播轉(zhuǎn)發(fā)次數(shù)，但難以通過選擇合適的轉(zhuǎn)發(fā)概率來保證全網(wǎng)覆蓋[5-6].有研究人員提出利用部分節(jié)點信息尋找最優(yōu)骨干轉(zhuǎn)發(fā)節(jié)點，減少廣播冗余，由于缺少有效的確認(rèn)機制，導(dǎo)致廣播業(yè)務(wù)大量重傳[7-8].有研究人員提出基于全網(wǎng)可靠廣播協(xié)議在單跳間采用編碼重傳技術(shù)降低廣播重傳開銷，但廣播的實時性難以保證，同時廣播業(yè)務(wù)的確認(rèn)開銷仍然較大[9-11].

針對可靠廣播業(yè)務(wù)中的上述問題，筆者提出一種基于多機會確認(rèn)的可靠廣播(multi-opportunities broadcast acknowledgement，簡稱MOAP)機制，利用無線信道的開放特性和兩跳鄰節(jié)點路由信息，通過轉(zhuǎn)發(fā)節(jié)點選擇、監(jiān)聽轉(zhuǎn)發(fā)、轉(zhuǎn)發(fā)捎帶及鄰節(jié)點輔助確認(rèn)4種方式，提高廣播業(yè)務(wù)確認(rèn)效率，減少可靠廣播傳輸時延和開銷，從而在較小代價下，保證無線網(wǎng)絡(luò)中廣播業(yè)務(wù)傳輸?shù)目煽啃?

1 多機會確認(rèn)機制的核心思想

基于廣播信道的開放性，對廣播業(yè)務(wù)進行確認(rèn)時，會同時啟動多個確認(rèn)分組的發(fā)送，進而造成確認(rèn)分組間的相互沖突，延長了確認(rèn)時延，降低了確認(rèn)效率[12-13].然而，利用其開放性，當(dāng)一個廣播業(yè)務(wù)在網(wǎng)絡(luò)中傳輸時，對于某一接收節(jié)點來說，可能多次接收到同一廣播業(yè)務(wù)分組.對特定廣播業(yè)務(wù)的確認(rèn)分組，其可能被多個節(jié)點接收.廣播業(yè)務(wù)傳輸時，利用廣播分組的上述重復(fù)接收特性，可降低分組的重傳概率.利用鄰節(jié)點對確認(rèn)分組的接收，幫助源節(jié)點完成確認(rèn).基于轉(zhuǎn)發(fā)節(jié)點的轉(zhuǎn)發(fā)，進行捎帶確認(rèn).若不對廣播業(yè)務(wù)在網(wǎng)絡(luò)中的傳輸加以約束，往往會在網(wǎng)絡(luò)中形成廣播風(fēng)暴，因此在進行多機會確認(rèn)時，還需對轉(zhuǎn)發(fā)節(jié)點進行選擇，以降低傳輸開銷和沖突概率.

圖1為多種確認(rèn)方式示意圖.源節(jié)點的一跳鄰節(jié)點分為轉(zhuǎn)發(fā)節(jié)點和非轉(zhuǎn)發(fā)節(jié)點.非轉(zhuǎn)發(fā)節(jié)點采用直接確認(rèn)方式向源節(jié)點回復(fù)確認(rèn)(acknowledge,簡稱ACK)(圖1(a))；轉(zhuǎn)發(fā)節(jié)點轉(zhuǎn)發(fā)廣播業(yè)務(wù)分組，源節(jié)點利用對轉(zhuǎn)發(fā)廣播業(yè)務(wù)分組的監(jiān)聽實現(xiàn)捎帶確認(rèn)(圖1(b))；非轉(zhuǎn)發(fā)節(jié)點回復(fù)的ACK同樣被轉(zhuǎn)發(fā)節(jié)點監(jiān)聽，轉(zhuǎn)發(fā)節(jié)點轉(zhuǎn)發(fā)廣播業(yè)務(wù)分組時捎帶其確認(rèn)信息，可協(xié)助源節(jié)點完成對確認(rèn)分組的接收，降低由于確認(rèn)分組傳輸失敗造成的重發(fā)(圖1(c))；當(dāng)非轉(zhuǎn)發(fā)節(jié)點未能正確接收廣播業(yè)務(wù)分組時，可再次利用轉(zhuǎn)發(fā)節(jié)點的轉(zhuǎn)發(fā)完成分組接收，此時該節(jié)點啟動確認(rèn)機制，完成源節(jié)點的確認(rèn)(圖1(d)).最后，針對未收到確認(rèn)分組信息的鄰節(jié)點，源節(jié)點需采用單播方式再次發(fā)送該廣播.

圖1 多種確認(rèn)方式示意圖

2 多機會確認(rèn)機制的關(guān)鍵技術(shù)

多機會確認(rèn)機制基于廣播信道的開放性，旨在提高可靠廣播業(yè)務(wù)確認(rèn)效率、降低廣播業(yè)務(wù)傳輸沖突和減少業(yè)務(wù)傳輸時延.在多機會確認(rèn)時，還應(yīng)考慮可靠轉(zhuǎn)發(fā)節(jié)點集合的選擇和多機會確認(rèn)時機等問題.

2.1 可靠轉(zhuǎn)發(fā)節(jié)點集合的選擇

借鑒虛擬骨干網(wǎng)的設(shè)計思想，選擇骨干節(jié)點進行廣播轉(zhuǎn)發(fā)，可明顯降低廣播開銷.在該文機制中，轉(zhuǎn)發(fā)節(jié)點的選擇，需考慮分組確認(rèn)問題.源節(jié)點在發(fā)起廣播分組時，啟動轉(zhuǎn)發(fā)節(jié)點選擇機制.

定義1源節(jié)點S所有兩跳范圍內(nèi)鄰節(jié)點集合為PS，所有一跳鄰節(jié)點集合為GS，則源節(jié)點兩跳鄰節(jié)點集合US=PS-GS.如果集合G中節(jié)點g1與集合U中節(jié)點u1間存在雙向傳輸路徑，則稱g1與u1間存在一條無向邊，簡稱g1與u1間存在一條邊.

定義2屬于集合GS且未收到該次廣播業(yè)務(wù)確認(rèn)分組的節(jié)點集合為一跳待確認(rèn)集合QS.

定義3集合RS為轉(zhuǎn)發(fā)節(jié)點集合，DS為非轉(zhuǎn)發(fā)集合，RS?GS且滿足下列條件：

(1) 集合U中所有節(jié)點均與集合R中至少一個節(jié)點間存在邊.

(2) 集合D=G-R.當(dāng)D不為空集時，D中所有節(jié)點均與集合R中至少一個節(jié)點間存在邊.

(3) 在滿足上述條件的情況下，集合R的基數(shù)最小.

圖2 轉(zhuǎn)發(fā)節(jié)點的選擇

2.2 多機會確認(rèn)時機的選擇

2.2.1 廣播的3種確認(rèn)機制

在廣播過程中，源節(jié)點通過3種機制來確認(rèn)周圍鄰節(jié)點是否收到了正確的廣播分組.3種機制分別為：直接收到廣播分組；源節(jié)點監(jiān)聽到鄰節(jié)點轉(zhuǎn)發(fā)廣播；源節(jié)點監(jiān)聽到轉(zhuǎn)發(fā)節(jié)點轉(zhuǎn)發(fā)廣播.

2.2.2 可靠廣播的確認(rèn)過程

多機會確認(rèn)過程如下：

(1) 對源節(jié)點S進行廣播分組，一跳范圍內(nèi)鄰節(jié)點集合G收到廣播分組，查看非廣播轉(zhuǎn)發(fā)中是否有自己的ID標(biāo)識，判斷自己是否需要回復(fù)廣播ACK.如果有自己的ID，依照ID順序在N+d(d為冗余間隔)個幀間隔內(nèi)回復(fù)廣播ACK.幀間隔時長為

t=WT，

(1)

(3) 轉(zhuǎn)發(fā)節(jié)點轉(zhuǎn)發(fā)時，源節(jié)點一跳范圍內(nèi)鄰節(jié)點第1次收到來自自己鄰節(jié)點S的廣播時，立即向源節(jié)點回復(fù)ACK.源節(jié)點S的待確認(rèn)集合Q中的節(jié)點，有多次確認(rèn)廣播分組業(yè)務(wù)可靠性的機會.多機會確認(rèn)機制的核心是源節(jié)點必須直接或間接確認(rèn)一跳范圍內(nèi)鄰節(jié)點是否正確收到廣播分組.

(4) 若一個確認(rèn)周期后，仍然有未確認(rèn)的鄰節(jié)點，為保證廣播業(yè)務(wù)的可靠性，可利用單播對未確認(rèn)節(jié)點進行補充確認(rèn).源節(jié)點S沒有監(jiān)聽到轉(zhuǎn)發(fā)節(jié)點L或E的轉(zhuǎn)發(fā)廣播時，立即對轉(zhuǎn)發(fā)節(jié)點L或E進行單播.若源節(jié)點在轉(zhuǎn)發(fā)結(jié)束后，既沒有收到鄰節(jié)點A的確認(rèn)分組，也沒有監(jiān)聽到轉(zhuǎn)發(fā)節(jié)點L轉(zhuǎn)發(fā)此廣播，源節(jié)點S應(yīng)立即對鄰節(jié)點A和L進行單播，并選擇它們作為轉(zhuǎn)發(fā)節(jié)點.

3 仿真驗證

在Ubuntu平臺上采用NS2仿真工具，對MOAP機制性能進行仿真，仿真參數(shù)如表1所示.

表1 仿真參數(shù)設(shè)置

仿真過程中，重點研究廣播業(yè)務(wù)的發(fā)送成功率和傳輸開銷.廣播遞交率(packet delivery ratio, 簡稱PDR)為

(2)

其中：m為接收到的有效消息數(shù)，n為應(yīng)接收的消息數(shù).

廣播開銷(broadcast overhead)為

(3)

其中：f為每個節(jié)點要發(fā)送的平均消息數(shù)，n為節(jié)點數(shù).

圖3是多機會確認(rèn)機制與基于IEEE 802.11的泛洪(flood)協(xié)議的廣播遞交率比較.從圖3可知，當(dāng)節(jié)點數(shù)增加，廣播遞交率也隨之增加[14].多機會廣播確認(rèn)機制的遞交率明顯優(yōu)于泛洪協(xié)議的，其平均遞交率比泛洪協(xié)議的高20%左右.在節(jié)點數(shù)較高時，多機會確認(rèn)機制的廣播遞交率可達100%.

MOAP機制采用端到端的確認(rèn)機制，可保證節(jié)點通信范圍內(nèi)所有節(jié)點廣播的可靠性.在節(jié)點較少的網(wǎng)絡(luò)場景中，網(wǎng)絡(luò)可能是間歇連通甚至非連通的，存在孤立節(jié)點，網(wǎng)絡(luò)的廣播遞交率比較低，MOAP機制可保證廣播的可靠性，而flood協(xié)議沒有有效的確認(rèn)機制，不能保證通信范圍內(nèi)廣播的可靠性[15].

隨著節(jié)點數(shù)增多，洪泛協(xié)議基于廣播信道的開放性，使接收節(jié)點能多次接收相同廣播分組，可提高廣播業(yè)務(wù)發(fā)送的可靠性.但是，隨著節(jié)點數(shù)增多，洪泛協(xié)議會產(chǎn)生大量的重復(fù)廣播業(yè)務(wù)，信道沖突加劇，降低了單次業(yè)務(wù)發(fā)送的成功概率.同時，由于未采用確認(rèn)機制，廣播業(yè)務(wù)傳輸中，對其可靠性的保證只能是“盡最大努力”完成，并不能保證每個廣播業(yè)務(wù)端到端發(fā)送的可靠性.MOAP機制引入了確認(rèn)機制和有限轉(zhuǎn)發(fā)機制，在減少網(wǎng)絡(luò)傳輸業(yè)務(wù)量、降低無線信道沖突的同時，保證了廣播業(yè)務(wù)端到端發(fā)送的可靠性.

圖4為多機會確認(rèn)機制與泛洪(flood)協(xié)議的廣播開銷比較.由圖4可知，當(dāng)節(jié)點數(shù)少時，兩者開銷幾乎一樣；隨著節(jié)點數(shù)增多，多機會確認(rèn)機制的廣播開銷遠(yuǎn)小于泛洪協(xié)議的廣播開銷.

圖3 廣播遞交率比較 圖4 廣播開銷比較

當(dāng)節(jié)點數(shù)少時，存在孤立的節(jié)點，多機會確認(rèn)機制要保證廣播的可靠性，需進行多次廣播業(yè)務(wù)，因此廣播開銷和泛洪協(xié)議的一樣大.在泛洪協(xié)議廣播中，隨著節(jié)點數(shù)增多，每個節(jié)點第1次收到廣播分組均會轉(zhuǎn)發(fā)此廣播分組，導(dǎo)致廣播開銷迅速增加、信道占用時間長、廣播沖突增大.MOAP機制選擇有效的鄰節(jié)點為轉(zhuǎn)發(fā)節(jié)點，在減少廣播開銷的同時，也使信道的利用率得以提高.

由仿真結(jié)果可知，無論節(jié)點數(shù)多少，多機會確認(rèn)機制的廣播遞交率明顯優(yōu)于泛洪協(xié)議，其廣播開銷也明顯優(yōu)于泛洪協(xié)議.

4 結(jié)束語

筆者提出了一種多機會確認(rèn)的無線網(wǎng)絡(luò)廣播機制，采用多機會確認(rèn)方法，選擇鄰節(jié)點轉(zhuǎn)發(fā)廣播，減少了廣播冗余，提高了廣播業(yè)務(wù)的可靠性.仿真結(jié)果表明，多機會廣播確認(rèn)機制在降低廣播開銷的同時，能提高廣播確認(rèn)的效率及廣播業(yè)務(wù)的可靠性，適用于廣播發(fā)布可靠性要求高的場景.