一種多機會確認的可靠廣播機制

一種多機會確認的可靠廣播機制

在web上，無線網(wǎng)絡(luò)無線網(wǎng)絡(luò)的低延遲和高可靠應(yīng)用場景中，傳統(tǒng)的基于網(wǎng)絡(luò)的服務(wù)協(xié)議很難在傳輸時間和費用最短的情況下確保網(wǎng)絡(luò)控制命令的傳輸。針對可靠廣播業(yè)務(wù)中的上述問題,筆者提出一種基于多機會確認的可靠廣播(multi-opportunitiesbroadcastacknowledgement,簡稱MOAP)機制,利用無線信道的開放特性和兩跳鄰節(jié)點路由信息,通過轉(zhuǎn)發(fā)節(jié)點選擇、監(jiān)聽轉(zhuǎn)發(fā)、轉(zhuǎn)發(fā)捎帶及鄰節(jié)點輔助確認4種方式,提高廣播業(yè)務(wù)確認效率,減少可靠廣播傳輸時延和開銷,從而在較小代價下,保證無線網(wǎng)絡(luò)中廣播業(yè)務(wù)傳輸?shù)目煽啃?1節(jié)點轉(zhuǎn)發(fā)廣播業(yè)務(wù)分組基于廣播信道的開放性,對廣播業(yè)務(wù)進行確認時,會同時啟動多個確認分組的發(fā)送,進而造成確認分組間的相互沖突,延長了確認時延,降低了確認效率圖1為多種確認方式示意圖.源節(jié)點的一跳鄰節(jié)點分為轉(zhuǎn)發(fā)節(jié)點和非轉(zhuǎn)發(fā)節(jié)點.非轉(zhuǎn)發(fā)節(jié)點采用直接確認方式向源節(jié)點回復(fù)確認(acknowledge,簡稱ACK)(圖1(a));轉(zhuǎn)發(fā)節(jié)點轉(zhuǎn)發(fā)廣播業(yè)務(wù)分組,源節(jié)點利用對轉(zhuǎn)發(fā)廣播業(yè)務(wù)分組的監(jiān)聽實現(xiàn)捎帶確認(圖1(b));非轉(zhuǎn)發(fā)節(jié)點回復(fù)的ACK同樣被轉(zhuǎn)發(fā)節(jié)點監(jiān)聽,轉(zhuǎn)發(fā)節(jié)點轉(zhuǎn)發(fā)廣播業(yè)務(wù)分組時捎帶其確認信息,可協(xié)助源節(jié)點完成對確認分組的接收,降低由于確認分組傳輸失敗造成的重發(fā)(圖1(c));當(dāng)非轉(zhuǎn)發(fā)節(jié)點未能正確接收廣播業(yè)務(wù)分組時,可再次利用轉(zhuǎn)發(fā)節(jié)點的轉(zhuǎn)發(fā)完成分組接收,此時該節(jié)點啟動確認機制,完成源節(jié)點的確認(圖1(d)).最后,針對未收到確認分組信息的鄰節(jié)點,源節(jié)點需采用單播方式再次發(fā)送該廣播.2可靠廣播業(yè)務(wù)確認多機會確認機制基于廣播信道的開放性,旨在提高可靠廣播業(yè)務(wù)確認效率、降低廣播業(yè)務(wù)傳輸沖突和減少業(yè)務(wù)傳輸時延.在多機會確認時,還應(yīng)考慮可靠轉(zhuǎn)發(fā)節(jié)點集合的選擇和多機會確認時機等問題.2.1圍內(nèi)鄰節(jié)點集合的確定借鑒虛擬骨干網(wǎng)的設(shè)計思想,選擇骨干節(jié)點進行廣播轉(zhuǎn)發(fā),可明顯降低廣播開銷.在該文機制中,轉(zhuǎn)發(fā)節(jié)點的選擇,需考慮分組確認問題.源節(jié)點在發(fā)起廣播分組時,啟動轉(zhuǎn)發(fā)節(jié)點選擇機制.定義1源節(jié)點S所有兩跳范圍內(nèi)鄰節(jié)點集合為P定義2屬于集合G定義3集合R(1)集合U中所有節(jié)點均與集合R中至少一個節(jié)點間存在邊.(3)在滿足上述條件的情況下,集合R的基數(shù)最小.如圖2所示,廣播確認過程中,源節(jié)點S及轉(zhuǎn)發(fā)節(jié)點內(nèi)部各建立一個一跳廣播待確認集Q,通過待確認集,保證一跳廣播的可靠性.源節(jié)點S的待確認集Q={A,B,C,D,E,L,M,N,O},即為一跳鄰節(jié)點集合G.圖2中所有節(jié)點均屬于源節(jié)點S的兩跳范圍鄰節(jié)點集合P,則兩跳鄰節(jié)點集合U=P-G={F,G,H,I,J,K}.被選擇的滿足條件的轉(zhuǎn)發(fā)節(jié)點集合R有多個,其中基數(shù)最小的為R={L,B,C,E},非轉(zhuǎn)發(fā)節(jié)點集合2.2更多地確認選擇時間2.2.1圍鄰節(jié)點是否接收廣播組分在廣播過程中,源節(jié)點通過3種機制來確認周圍鄰節(jié)點是否收到了正確的廣播分組.3種機制分別為:直接收到廣播分組;源節(jié)點監(jiān)聽到鄰節(jié)點轉(zhuǎn)發(fā)廣播;源節(jié)點監(jiān)聽到轉(zhuǎn)發(fā)節(jié)點轉(zhuǎn)發(fā)廣播.2.2.2可靠廣播的確認多機會確認過程如下:(1)對源節(jié)點S進行廣播分組,一跳范圍內(nèi)鄰節(jié)點集合G收到廣播分組,查看非廣播轉(zhuǎn)發(fā)中是否有自己的ID標識,判斷自己是否需要回復(fù)廣播ACK.如果有自己的ID,依照ID順序在N+d(d為冗余間隔)個幀間隔內(nèi)回復(fù)廣播ACK.幀間隔時長為其中:WT(waitingtime)為鄰節(jié)點廣播傳輸時延的兩倍.源節(jié)點收到廣播ACK時,從一跳待確認集中去除該鄰節(jié)點,便可保證非轉(zhuǎn)發(fā)待確認節(jié)點集合(2)作為轉(zhuǎn)發(fā)集合R中的節(jié)點,當(dāng)轉(zhuǎn)發(fā)節(jié)點收到廣播報文時,查看報文中需要直接回復(fù)ACK的非轉(zhuǎn)發(fā)節(jié)點的ID,若非轉(zhuǎn)發(fā)節(jié)點是此轉(zhuǎn)發(fā)節(jié)點的一跳鄰節(jié)點,則監(jiān)聽此節(jié)點是否回復(fù)ACK.轉(zhuǎn)發(fā)節(jié)點轉(zhuǎn)發(fā)廣播報文時,在報文的標識位flag上標識是否收到非轉(zhuǎn)發(fā)節(jié)點的回復(fù)ACK.轉(zhuǎn)發(fā)節(jié)點進行轉(zhuǎn)發(fā)廣播業(yè)務(wù)時,同樣根據(jù)鄰節(jié)點的定義,選擇下一跳的轉(zhuǎn)發(fā)節(jié)點,更新并轉(zhuǎn)發(fā)廣播報文,源節(jié)點通過監(jiān)聽轉(zhuǎn)發(fā)節(jié)點是否轉(zhuǎn)發(fā)了此廣播分組,間接確認集合R節(jié)點的廣播可靠性,同時查看非轉(zhuǎn)發(fā)節(jié)點的回復(fù)標識位,對非轉(zhuǎn)發(fā)待確認集合(3)轉(zhuǎn)發(fā)節(jié)點轉(zhuǎn)發(fā)時,源節(jié)點一跳范圍內(nèi)鄰節(jié)點第1次收到來自自己鄰節(jié)點S的廣播時,立即向源節(jié)點回復(fù)ACK.源節(jié)點S的待確認集合Q中的節(jié)點,有多次確認廣播分組業(yè)務(wù)可靠性的機會.多機會確認機制的核心是源節(jié)點必須直接或間接確認一跳范圍內(nèi)鄰節(jié)點是否正確收到廣播分組.(4)若一個確認周期后,仍然有未確認的鄰節(jié)點,為保證廣播業(yè)務(wù)的可靠性,可利用單播對未確認節(jié)點進行補充確認.源節(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的確認分組,也沒有監(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所示.仿真過程中,重點研究廣播業(yè)務(wù)的發(fā)送成功率和傳輸開銷.廣播遞交率(packetdeliveryratio,簡稱PDR)為其中:m為接收到的有效消息數(shù),n為應(yīng)接收的消息數(shù).廣播開銷(broadcastoverhead)為其中:f為每個節(jié)點要發(fā)送的平均消息數(shù),n為節(jié)點數(shù).圖3是多機會確認機制與基于IEEE802.11的泛洪(flood)協(xié)議的廣播遞交率比較.從圖3可知,當(dāng)節(jié)點數(shù)增加,廣播遞交率也隨之增加MOAP機制采用端到端的確認機制,可保證節(jié)點通信范圍內(nèi)所有節(jié)點廣播的可靠性.在節(jié)點較少的網(wǎng)絡(luò)場景中,網(wǎng)絡(luò)可能是間歇連通甚至非連通的,存在孤立節(jié)點,網(wǎng)絡(luò)的廣播遞交率比較低,MOAP機制可保證廣播的可靠性,而flood協(xié)議沒有有效的確認機制,不能保證通信范圍內(nèi)廣播的可靠性隨著節(jié)點數(shù)增多,洪泛協(xié)議基于廣播信道的開放性,使接收節(jié)點能多次接收相同廣播分組,可提高廣播業(yè)務(wù)發(fā)送的可靠性.但是,隨著節(jié)點數(shù)增多,洪泛協(xié)議會產(chǎn)生大量的重復(fù)廣播業(yè)務(wù),信道沖突加劇,降低了單次業(yè)務(wù)發(fā)送的成功概率.同時,由于未采用確認機制,廣播業(yè)務(wù)傳輸中,對其可靠性的保證只能是“盡最大努力”完成,并不能保證每個廣播業(yè)務(wù)端到端發(fā)送的可靠性.MOAP機制引入了確認機制和有限轉(zhuǎn)發(fā)機制,在減少網(wǎng)絡(luò)傳輸業(yè)務(wù)量、降低無線信道沖突的同時,保證了廣播業(yè)務(wù)端到端發(fā)送的可靠性.圖4為多機會確認機制與泛洪(flood)協(xié)議的廣播開銷比較.由圖4可知,當(dāng)節(jié)點數(shù)少時,兩者開銷幾乎一樣;隨著節(jié)點數(shù)增多,多機會確認機制的廣播開銷遠小于泛洪協(xié)議的廣播開銷.當(dāng)節(jié)點數(shù)少時,存在孤立的節(jié)點,多機會確認機制要保證廣播的可靠性,需進行多次廣播業(yè)務(wù),因此廣播開銷和泛洪協(xié)議的一樣大.在泛洪協(xié)議廣播中,隨著節(jié)點數(shù)增多,每個節(jié)點第1次收到廣播分組均會轉(zhuǎn)發(fā)此廣播分組,導(dǎo)致廣播開銷迅速增加、信道占用時間長、廣播沖突增大.MOAP機制選擇有效的鄰節(jié)點為轉(zhuǎn)發(fā)節(jié)點,在減少廣播開銷的同時,也使信道的利用率得以提高.由仿真結(jié)果可知,無論節(jié)點數(shù)多少,多機會確認機制的廣播遞交率明顯優(yōu)于泛洪協(xié)議,其廣播開銷也明顯優(yōu)于泛洪協(xié)議.4廣播確認機制筆者提出了一種多機會確認的無