多跳無線網(wǎng)絡(luò)中的廣播

多跳無線網(wǎng)絡(luò)中的廣播

1tfb算法的基本原理廣播操作是多段無線網(wǎng)絡(luò)的基本功能。其傳統(tǒng)的實(shí)現(xiàn)方法——洪泛(flooding)協(xié)議無線網(wǎng)絡(luò)中除了存在大量的沖突和擁塞外,還容易出現(xiàn)傳輸錯(cuò)誤。因此,要實(shí)現(xiàn)可靠的廣播存在很大的困難本文的目的是在保證較高送達(dá)率的前提下,盡可能地減少轉(zhuǎn)發(fā)次數(shù)。文中首先分析了在節(jié)點(diǎn)理想分布的網(wǎng)絡(luò)中實(shí)現(xiàn)全網(wǎng)覆蓋所需的最小節(jié)點(diǎn)數(shù)目,并找到利用最少數(shù)目的轉(zhuǎn)發(fā)節(jié)點(diǎn)實(shí)現(xiàn)對(duì)整個(gè)網(wǎng)絡(luò)雙重覆蓋的方法,在此基礎(chǔ)上提出一種3點(diǎn)轉(zhuǎn)發(fā)的廣播(TripleForwardingBroadcast,TFB)算法。與以往的方法相比,TFB算法具有如下優(yōu)點(diǎn):(1)每個(gè)節(jié)點(diǎn)最多只需選擇三個(gè)最優(yōu)的轉(zhuǎn)發(fā)節(jié)點(diǎn),明顯提高了轉(zhuǎn)發(fā)效率;(2)所有轉(zhuǎn)發(fā)節(jié)點(diǎn)實(shí)現(xiàn)了對(duì)整個(gè)網(wǎng)絡(luò)區(qū)域接近雙重的覆蓋,能夠提供較高的傳輸送達(dá)率;(3)具有良好的可擴(kuò)展性,適于大規(guī)模的網(wǎng)絡(luò)和拓?fù)鋭×易兓沫h(huán)境;(4)僅使用一跳鄰居信息并且所需的計(jì)算量很小,因而減小了協(xié)議的開銷,易于實(shí)現(xiàn)。2節(jié)點(diǎn)密度和傳輸半徑本文研究大型網(wǎng)絡(luò),即網(wǎng)絡(luò)在任意方向的長(zhǎng)度遠(yuǎn)遠(yuǎn)大于節(jié)點(diǎn)的傳輸半徑。假設(shè)網(wǎng)絡(luò)是連通的并且節(jié)點(diǎn)密度足夠大;所有節(jié)點(diǎn)具有相同的傳輸半徑R。假設(shè)節(jié)點(diǎn)通過GPS等方式知道自己所處的絕對(duì)位置。每個(gè)節(jié)點(diǎn)可以通過節(jié)點(diǎn)周期性的發(fā)送hello消息獲得一跳鄰居信息,包括節(jié)點(diǎn)ID和節(jié)點(diǎn)位置。2.1網(wǎng)絡(luò)結(jié)構(gòu)及網(wǎng)格劃分定理1在網(wǎng)絡(luò)節(jié)點(diǎn)分布理想的情況下,圖1(b)中所示的轉(zhuǎn)發(fā)節(jié)點(diǎn)分布方式能夠用最少數(shù)目的轉(zhuǎn)發(fā)節(jié)點(diǎn)實(shí)現(xiàn)對(duì)網(wǎng)絡(luò)無縫的覆蓋,所需的轉(zhuǎn)發(fā)節(jié)點(diǎn)個(gè)數(shù)為9n(n+1)/2,其中n=1,2,3為圖1(a)中所示的包圍源節(jié)點(diǎn)S所需的轉(zhuǎn)發(fā)節(jié)點(diǎn)層數(shù)。證明首先引入使用最少個(gè)數(shù)的半徑為R的圓盤無縫地覆蓋整個(gè)平面的問題。Kershner為了完成轉(zhuǎn)發(fā),必須使這些節(jié)點(diǎn)互相連接。使兩個(gè)節(jié)點(diǎn)互相連接必須在兩個(gè)圓盤的相交區(qū)域增加轉(zhuǎn)發(fā)節(jié)點(diǎn)。令S與第1層節(jié)點(diǎn)連接最少需要3個(gè)節(jié)點(diǎn),此時(shí)連接節(jié)點(diǎn)落在中心圓盤與其他兩個(gè)圓盤的公共交點(diǎn),可以同時(shí)使S與兩個(gè)第1層節(jié)點(diǎn)連接。同理,第1層與第2層連接最少需要6個(gè)節(jié)點(diǎn),如圖1(b)所示。每?jī)蓪娱g需要增加的節(jié)點(diǎn)個(gè)數(shù)為除源節(jié)點(diǎn)所在的圓盤以外,圓盤的個(gè)數(shù)可表示為兩個(gè)等差數(shù)列分別為式(1)和式(2)。所以,總的圓盤個(gè)數(shù)即覆蓋網(wǎng)絡(luò)所需的最少轉(zhuǎn)發(fā)節(jié)點(diǎn)個(gè)數(shù)為證畢圖1(b)所示的轉(zhuǎn)發(fā)節(jié)點(diǎn)組成的子網(wǎng)中,每一個(gè)節(jié)點(diǎn)與其他兩個(gè)或3個(gè)節(jié)點(diǎn)相連,這種結(jié)構(gòu)具有最優(yōu)的轉(zhuǎn)發(fā)效率。但其中每個(gè)連接都是非冗余的,任何一個(gè)節(jié)點(diǎn)的傳輸錯(cuò)誤都會(huì)導(dǎo)致部分節(jié)點(diǎn)丟包甚至無法繼續(xù)轉(zhuǎn)發(fā)。為了改善這一問題,提高可靠性,本文提出了定理2中利用最少個(gè)數(shù)的轉(zhuǎn)發(fā)節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)進(jìn)行雙重覆蓋的方法,與圖1(b)所示的最優(yōu)覆蓋方法相比,這種方法通過增加很少的轉(zhuǎn)發(fā)節(jié)點(diǎn)實(shí)現(xiàn)了對(duì)網(wǎng)絡(luò)的雙重覆蓋,并且任意兩個(gè)節(jié)點(diǎn)之間都有至少3條路徑相連,增強(qiáng)了容錯(cuò)能力。定理2在節(jié)點(diǎn)分布理想的網(wǎng)絡(luò)中,將網(wǎng)絡(luò)平面劃分為正六邊形的網(wǎng)格,在每個(gè)六邊形頂點(diǎn)處分別有一個(gè)轉(zhuǎn)發(fā)節(jié)點(diǎn),如圖2(a)所示。這種轉(zhuǎn)發(fā)節(jié)點(diǎn)分布方式能夠用最少個(gè)數(shù)的轉(zhuǎn)發(fā)節(jié)點(diǎn)實(shí)現(xiàn)對(duì)整個(gè)網(wǎng)絡(luò)的雙重覆蓋,其中每個(gè)轉(zhuǎn)發(fā)節(jié)點(diǎn)與其他3個(gè)轉(zhuǎn)發(fā)節(jié)點(diǎn)相連接。證明將圖1(a)中所有圓盤圓心位置移動(dòng)到對(duì)應(yīng)六邊形的同一方位的頂點(diǎn),可得到圖2(b)或圖2(c)所示的兩種排列方式,這兩種排列方式均等價(jià)于圖1(a)中所示的方式。將這兩組圓盤按照網(wǎng)格對(duì)齊疊加在一起,即得到圖2(a)所示的節(jié)點(diǎn)分布。這種轉(zhuǎn)發(fā)節(jié)點(diǎn)的分布方式實(shí)現(xiàn)了最高效率的雙重覆蓋,并且任意兩點(diǎn)之間都有至少3條路徑相連。此外,圓盤之間的重疊面積最小,并可按式(4),式(5)計(jì)算得到。兩個(gè)節(jié)點(diǎn)傳輸范圍的重疊面積(如圖3所示)為其中d為兩節(jié)點(diǎn)之間的距離;圖2(a)中每個(gè)傳輸范圍內(nèi)總的重疊面積為證畢33轉(zhuǎn)發(fā)節(jié)點(diǎn)的選擇由圖2(a)中的轉(zhuǎn)發(fā)節(jié)點(diǎn)結(jié)構(gòu)我們提出了3點(diǎn)轉(zhuǎn)發(fā)廣播算法(TFB)。實(shí)際的網(wǎng)絡(luò)不能得到這種理想的拓?fù)?當(dāng)轉(zhuǎn)發(fā)節(jié)點(diǎn)不在最佳位置時(shí),覆蓋效果會(huì)出現(xiàn)偏差。當(dāng)轉(zhuǎn)發(fā)節(jié)點(diǎn)距離較近時(shí),會(huì)產(chǎn)生更多的重疊覆蓋區(qū)域但不會(huì)影響其連接性;而且,只要保證節(jié)點(diǎn)分布的方向盡量對(duì)稱,就可以盡量完全地覆蓋網(wǎng)絡(luò)。因此選擇轉(zhuǎn)發(fā)節(jié)點(diǎn)的思想是使每個(gè)節(jié)點(diǎn)盡量靠近3個(gè)理想方向并且具有盡可能大的附加覆蓋面積(AdditionalCoveredarea,ACTFB協(xié)議的工作過程:源節(jié)點(diǎn)在發(fā)送數(shù)據(jù)包時(shí),首先選擇3個(gè)最優(yōu)的鄰節(jié)點(diǎn)作為轉(zhuǎn)發(fā)節(jié)點(diǎn),將轉(zhuǎn)發(fā)節(jié)點(diǎn)列表附加在數(shù)據(jù)包頭中,然后廣播該數(shù)據(jù)包。鄰居節(jié)點(diǎn)接收到數(shù)據(jù)包后,檢查是否已接收過,如果是則丟棄;否則將該包轉(zhuǎn)交至上層協(xié)議,然后檢查是否需要轉(zhuǎn)發(fā)此包,如果是則選擇另外兩個(gè)轉(zhuǎn)發(fā)節(jié)點(diǎn)加入節(jié)點(diǎn)列表并轉(zhuǎn)發(fā)該包。所有節(jié)點(diǎn)重復(fù)此過程直到數(shù)據(jù)包到達(dá)網(wǎng)絡(luò)邊緣。3.1位置函數(shù)源節(jié)點(diǎn)首先計(jì)算到每個(gè)鄰居的距離,并選擇距離最遠(yuǎn)的節(jié)點(diǎn)作為第一個(gè)轉(zhuǎn)發(fā)節(jié)點(diǎn),用N和一個(gè)位置函數(shù)角度函數(shù)描述了節(jié)點(diǎn)接近最優(yōu)方向的程度,如圖5所示,其函數(shù)值在0,2π/3,4π/3三個(gè)方向最大。位置函數(shù)用來描述節(jié)點(diǎn)位置與最佳位置的接近程度,節(jié)點(diǎn)的位置函數(shù)值越大越接近圖2(a)中所示的最佳位置。轉(zhuǎn)發(fā)節(jié)點(diǎn)選擇過程:源節(jié)點(diǎn)首先計(jì)算并選擇距離最大的鄰節(jié)點(diǎn)作為N3.2相近節(jié)點(diǎn)的選擇實(shí)際網(wǎng)絡(luò)拓?fù)渑c理想節(jié)點(diǎn)分布存在偏差,而且轉(zhuǎn)發(fā)節(jié)點(diǎn)在每個(gè)節(jié)點(diǎn)本地最優(yōu)選擇,這會(huì)造成不同的節(jié)點(diǎn)在相近位置選擇兩個(gè)轉(zhuǎn)發(fā)節(jié)點(diǎn)(在理想分布時(shí)是同一個(gè)節(jié)點(diǎn))。本文稱這種現(xiàn)象為相近節(jié)點(diǎn)。相近節(jié)點(diǎn)會(huì)產(chǎn)生傳輸冗余并且這種現(xiàn)象會(huì)蔓延,我們引入一個(gè)門限值d4tfb傳輸范圍對(duì)轉(zhuǎn)發(fā)節(jié)點(diǎn)數(shù)目的影響我們將TFB的性能與其他3種協(xié)議進(jìn)行了仿真比較,3種協(xié)議分別是洪泛協(xié)議(Pureflooding)實(shí)驗(yàn)1節(jié)點(diǎn)密度對(duì)協(xié)議性能的影響仿真條件為:200到1000個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)隨機(jī)分布在面積為1000m×1000m的正方形區(qū)域內(nèi)。節(jié)點(diǎn)傳輸范圍為250m。節(jié)點(diǎn)最大速度為20m/s。仿真結(jié)果示于圖6和圖7。圖6顯示TFB的性能明顯優(yōu)于其他對(duì)比協(xié)議。由于TFB能提供幾乎雙重的傳輸覆蓋,當(dāng)節(jié)點(diǎn)數(shù)較少時(shí)能獲得接近100%的送達(dá)率。當(dāng)節(jié)點(diǎn)密度增大是,網(wǎng)絡(luò)中出現(xiàn)較多的沖突,因而所有協(xié)議的送達(dá)率降低,其中TFB協(xié)議的降低較小,當(dāng)節(jié)點(diǎn)數(shù)目為1000時(shí)仍然獲得大于95%的送達(dá)率。這是由于TFB使用很少的轉(zhuǎn)發(fā)節(jié)點(diǎn),相對(duì)其他協(xié)議表現(xiàn)出更好的優(yōu)勢(shì)。圖7中,TFB協(xié)議的轉(zhuǎn)發(fā)效率與其他協(xié)議相比具有很大的改善,對(duì)所有節(jié)點(diǎn)數(shù)轉(zhuǎn)發(fā)率都不超過10%。在TFB中,轉(zhuǎn)發(fā)節(jié)點(diǎn)的數(shù)目只與網(wǎng)絡(luò)范圍相關(guān),并且當(dāng)節(jié)點(diǎn)密度增大時(shí),轉(zhuǎn)發(fā)節(jié)點(diǎn)數(shù)目減少并趨于最低值,節(jié)點(diǎn)的分布也趨于最優(yōu)分布。實(shí)驗(yàn)2節(jié)點(diǎn)傳輸范圍對(duì)協(xié)議性能的影響仿真的運(yùn)行條件為:1000個(gè)節(jié)點(diǎn)隨機(jī)分布在1000m×1000m的網(wǎng)絡(luò)區(qū)域內(nèi)。節(jié)點(diǎn)的傳輸范圍分別設(shè)為100m到300m。節(jié)點(diǎn)最大速度仍為20m/s。仿真結(jié)果示于圖8和圖9。由圖8可以看到,TFB在節(jié)點(diǎn)傳輸范圍變化時(shí)性能均明顯優(yōu)于其他3種協(xié)議,在傳輸范圍為100m時(shí)能提供大于95%的送達(dá)率,300m時(shí)接近100%;而洪泛協(xié)議、邊緣轉(zhuǎn)發(fā)協(xié)議和基于CDS的廣播協(xié)議的送達(dá)率在節(jié)點(diǎn)傳輸范圍較小時(shí)都比較低。隨著傳輸范圍增大所有協(xié)議的送達(dá)率逐漸增大,這是由于節(jié)點(diǎn)傳輸范圍增大時(shí),一方面會(huì)造成較多的沖突,同時(shí)也增加了節(jié)點(diǎn)收到包的機(jī)會(huì)。圖9中的結(jié)果顯示了TFB在不同傳輸范圍時(shí)的轉(zhuǎn)發(fā)效率明顯優(yōu)于其他兩種協(xié)議。其結(jié)果與圖7中類似,這是由于傳輸范圍增大同樣使節(jié)點(diǎn)密度增大,與節(jié)點(diǎn)數(shù)目增加具有類似的效果;同時(shí),傳輸范圍增大時(shí)廣播操作所需的跳數(shù)減少,從而減少了轉(zhuǎn)發(fā)節(jié)點(diǎn)的數(shù)目。這兩種仿真試驗(yàn)的結(jié)果也表明:TFB更適合于節(jié)點(diǎn)密集的網(wǎng)絡(luò)。實(shí)驗(yàn)3TFB協(xié)議的可擴(kuò)展性本文還針對(duì)不同的網(wǎng)絡(luò)規(guī)模和節(jié)點(diǎn)速度分別運(yùn)行了TFB協(xié)議。網(wǎng)絡(luò)規(guī)模通過相同節(jié)點(diǎn)密度但不同的節(jié)點(diǎn)數(shù)和網(wǎng)絡(luò)面積反映。運(yùn)行條件為:節(jié)點(diǎn)數(shù)目分別為200,400,800和1600,對(duì)應(yīng)的正方形網(wǎng)絡(luò)區(qū)域邊長(zhǎng)分別為1000m,1414m,2000m和2828m;節(jié)點(diǎn)最大速度為20m/s;傳輸范圍為250m。結(jié)果示于圖10。不同節(jié)點(diǎn)速度反應(yīng)網(wǎng)絡(luò)拓?fù)涞淖兓潭?最大節(jié)點(diǎn)速度分別設(shè)置為1,5,10,20和40m/s。節(jié)點(diǎn)數(shù)為500,網(wǎng)絡(luò)面積為1000m×1000m。傳輸范圍同樣為250m。其結(jié)果顯示于圖11。由圖10可以看到,對(duì)于不同的網(wǎng)絡(luò)規(guī)模TFB的性能均表現(xiàn)良好(送達(dá)率接近100%,而轉(zhuǎn)發(fā)率維持在10%左右),在網(wǎng)絡(luò)面積增大時(shí)無明顯變化。這得益于TFB采用極少的轉(zhuǎn)發(fā)節(jié)點(diǎn)個(gè)數(shù)。圖11顯示出類似的結(jié)果,TFB的性能不受節(jié)點(diǎn)速度影響。這是由于TFB采用一跳鄰居信息,能夠?qū)崟r(shí)更新;并且轉(zhuǎn)發(fā)節(jié)點(diǎn)的選擇基于每一個(gè)數(shù)據(jù)包,使得轉(zhuǎn)發(fā)節(jié)點(diǎn)總是處于最優(yōu)的位置。此仿真結(jié)果說明TFB具有良好的可擴(kuò)展性,適用于大規(guī)模的網(wǎng)絡(luò)或拓?fù)鋭×易兓沫h(huán)境。5點(diǎn)轉(zhuǎn)發(fā)廣播算法tfb多跳無線網(wǎng)絡(luò)中廣播操作的傳輸冗余會(huì)產(chǎn)生額外的網(wǎng)絡(luò)負(fù)載,增加信號(hào)沖突甚至使網(wǎng)絡(luò)擁塞。除此之外,傳輸范圍