秦 娜,劉宴濤
(1.嘉應(yīng)學(xué)院計(jì)算機(jī)學(xué)院,廣東 梅州 514015;2.蒙古研究大學(xué))
無線自組織網(wǎng)絡(luò),簡稱無線自組網(wǎng)(Ad hoc Network),又稱移動(dòng)自組網(wǎng)(MANET-Mobile Ad hoc Network),是一種特殊的無線網(wǎng)絡(luò)形式。這種網(wǎng)絡(luò)為某種特殊應(yīng)用或特殊目的而構(gòu)建,由一組帶有無線收發(fā)信機(jī)的移動(dòng)終端組成,網(wǎng)絡(luò)節(jié)點(diǎn)同時(shí)充當(dāng)終端主機(jī)和路由器的角色,結(jié)合了計(jì)算機(jī)網(wǎng)絡(luò)和無線通信的優(yōu)勢(shì),具有無中心、自組織、多跳路由、動(dòng)態(tài)拓?fù)洹⒖焖俨荚O(shè)、不依賴基礎(chǔ)設(shè)施、體積小、能耗低、分布式、合作通信、高抗毀、可移動(dòng)、可重組等特點(diǎn)。無線自組網(wǎng)與傳感器網(wǎng)絡(luò)、物聯(lián)網(wǎng)等無線網(wǎng)絡(luò)技術(shù)具有密切的聯(lián)系,其主要應(yīng)用場(chǎng)合有搶險(xiǎn)救災(zāi)、戰(zhàn)場(chǎng)通信、野外救援、會(huì)議慶典、水庫、礦山、公安、消防、森林防火和公共交通等。
應(yīng)急通信網(wǎng)絡(luò)是無線自組網(wǎng)在民用領(lǐng)域的一種典型應(yīng)用,這種網(wǎng)絡(luò)主要應(yīng)用于地震、洪水、泥石流等災(zāi)難之后臨時(shí)創(chuàng)建應(yīng)急通信保障。以地震為例,災(zāi)害過后由于電力、通信等基礎(chǔ)設(shè)施損毀殆盡,災(zāi)難現(xiàn)場(chǎng)的情況無法及時(shí)為外界獲知,給快速有效的施救造成了極大的困難。地震過后搶救生命意味著與時(shí)間賽跑,如果震后超過了72 小時(shí),人員生還的希望就很渺茫,所以快速準(zhǔn)確地采集到震區(qū)的實(shí)時(shí)情況(比如人體紅外、聲音、圖像、視頻、生命體征等)是災(zāi)難救助的首要任務(wù)。這就把不依賴于基礎(chǔ)設(shè)施、快速、自動(dòng)的通信保障的重要性提到了前所未有的高度,而無線自組網(wǎng)正好符合了這一要求。
應(yīng)急通信網(wǎng)絡(luò)的研究重點(diǎn)包括寬帶無線接入、單/組/廣播路由算法、網(wǎng)絡(luò)的覆蓋性和連通性、移動(dòng)性管理、功率控制等等??凳匦臶1]針對(duì)礦井下多點(diǎn)應(yīng)急救援研究了基于無線Mesh網(wǎng)絡(luò)的應(yīng)急通信基站,提出了應(yīng)急通信基站無線中繼與無線覆蓋的方案,并對(duì)應(yīng)急通信基站的最大傳輸距離進(jìn)行了模擬仿真。王魯寧[2]提出了系統(tǒng)化、扁平化、智能化的感知網(wǎng)絡(luò)全覆蓋的現(xiàn)代應(yīng)急管理體系的建設(shè)思路。賀燦輝[3]結(jié)合消防應(yīng)急通信構(gòu)建Mesh 網(wǎng)絡(luò)以提高消防應(yīng)急的質(zhì)量和安全性。肖強(qiáng)[4]對(duì)應(yīng)急通信技術(shù)的發(fā)展、特點(diǎn)和趨勢(shì)進(jìn)行綜述。周雄偉[5]通過對(duì)應(yīng)急通信和公共通信的特點(diǎn)比較,提出了應(yīng)急通信的服務(wù)保障模式,并對(duì)應(yīng)急通信標(biāo)準(zhǔn)規(guī)范給出建議。姜海涵[6]針對(duì)信道吞吐量低、阻塞率高等問題,提出了應(yīng)急通信異構(gòu)網(wǎng)絡(luò)的信道選擇方法。張昊曄[7]基于認(rèn)知無線電技術(shù),提出了不同任務(wù)策略下的優(yōu)化目標(biāo)和約束條件,實(shí)現(xiàn)網(wǎng)絡(luò)效能最大化。
可靠性和有效性是應(yīng)急通信網(wǎng)的兩項(xiàng)重要指標(biāo),前者表示信源發(fā)出的數(shù)據(jù)包能準(zhǔn)確可靠地為所有信宿接收,后者表示網(wǎng)絡(luò)的傳輸速率快、資源消耗少。然而在實(shí)際應(yīng)用中這兩者往往是一對(duì)矛盾,為了提高可靠性,需要增加節(jié)點(diǎn)轉(zhuǎn)發(fā)概率,減少丟包率,而這又不可避免地加劇信號(hào)沖突和信道資源占用,降低有效性。為了調(diào)和這兩者的矛盾,本文提出了一種加權(quán)的概率廣播算法,通過引入加權(quán)系數(shù)和目標(biāo)函數(shù)取得有效性和可靠性的折中。
本文的后續(xù)如下:第1 節(jié)通過仿真實(shí)驗(yàn)測(cè)算節(jié)點(diǎn)度和網(wǎng)絡(luò)連通度的關(guān)系,為概率廣播實(shí)驗(yàn)的節(jié)點(diǎn)密度提供定量依據(jù);第2 節(jié)介紹概率廣播的基本原理并解釋相變現(xiàn)象;第3節(jié)提出了加權(quán)的概率廣播算法,通過引入加權(quán)系數(shù)和目標(biāo)函數(shù)在有效性和可靠性之間進(jìn)行折中,通過大量仿真實(shí)驗(yàn)測(cè)算最優(yōu)廣播概率,并通過仿真實(shí)驗(yàn)來對(duì)比加權(quán)概率廣播和普通廣播;第4 節(jié)給出本文的結(jié)論。
連通性是應(yīng)急通信網(wǎng)絡(luò)的重要指標(biāo),所有路由算法的有效性都是以網(wǎng)絡(luò)連通為前提的。影響網(wǎng)絡(luò)連通性的因素有很多,如網(wǎng)絡(luò)的拓?fù)浜透采w范圍,節(jié)點(diǎn)的數(shù)目和通信半徑,對(duì)于移動(dòng)網(wǎng)絡(luò)還包括節(jié)點(diǎn)的移動(dòng)性。因此,很難對(duì)網(wǎng)絡(luò)連通性做出精確的理論分析。本節(jié)應(yīng)用Ad hoc 網(wǎng)絡(luò)仿真工具箱ANSim,對(duì)網(wǎng)絡(luò)連通性做仿真研究。
網(wǎng)絡(luò)連通概率與網(wǎng)絡(luò)平均度有關(guān)。節(jié)點(diǎn)u的度是指與u直接相連的節(jié)點(diǎn)數(shù)目,全部節(jié)點(diǎn)度的平均值稱為網(wǎng)絡(luò)的平均度。假設(shè)網(wǎng)絡(luò)覆蓋面積為S,節(jié)點(diǎn)的通信半徑為R,節(jié)點(diǎn)數(shù)目為n,則網(wǎng)絡(luò)平均度由式⑴決定。
仿真實(shí)驗(yàn)1:n個(gè)節(jié)點(diǎn)均勻分布在1000m×1000m的矩形范圍內(nèi),節(jié)點(diǎn)通信半徑為250m,節(jié)點(diǎn)采取隨機(jī)點(diǎn)移動(dòng)模型。通過調(diào)整n的值并通過公式⑴計(jì)算得到一組平均度k的值,應(yīng)用ANSim 的統(tǒng)計(jì)功能可以得到網(wǎng)絡(luò)連通概率(即網(wǎng)絡(luò)最大連通組中節(jié)點(diǎn)數(shù)占全部節(jié)點(diǎn)數(shù)的比例)和平均度k的關(guān)系曲線,如圖1 所示。由此可見,網(wǎng)絡(luò)連通概率隨著節(jié)點(diǎn)度的增加而提高,當(dāng)節(jié)點(diǎn)度達(dá)到6 時(shí),網(wǎng)絡(luò)連通概率已超過95%,表現(xiàn)出很健壯的連通性。
圖1 網(wǎng)絡(luò)連通概率和節(jié)點(diǎn)平均度的關(guān)系
泛洪廣播,簡稱泛洪,是一種廣播路由技術(shù),是指數(shù)據(jù)包從源節(jié)點(diǎn)發(fā)出后,所有收到該數(shù)據(jù)包的中間節(jié)點(diǎn)對(duì)其進(jìn)行中繼轉(zhuǎn)發(fā),一級(jí)一級(jí)地向后傳遞,像洪水泛濫一樣,直到所有節(jié)點(diǎn)都收到該數(shù)據(jù)包為止。泛洪可以單獨(dú)作為路由算法使用,也可以輔助其他路由算法,比如動(dòng)態(tài)源路由DSR(Dynamic Source Routing)、按需組播路由協(xié)議ODMRP(OnDemand Multicast Routing Proto-col),用于這些路由的建立與更新。
普通的泛洪廣播算法中,中間節(jié)點(diǎn)以概率1 轉(zhuǎn)發(fā)數(shù)據(jù)包,網(wǎng)絡(luò)中會(huì)出現(xiàn)大量的數(shù)據(jù)包,造成劇烈的信號(hào)沖突和信道浪費(fèi)。概率廣播[8]可以緩解這一問題,所謂概率廣播是指中間節(jié)點(diǎn)收到上游節(jié)點(diǎn)發(fā)來的數(shù)據(jù)包后以概率p轉(zhuǎn)發(fā)該數(shù)據(jù)包。下面基于OPNET 設(shè)計(jì)一組仿真實(shí)驗(yàn)驗(yàn)證泛洪概率p對(duì)于廣播算法的影響。
仿真實(shí)驗(yàn)2:如圖2 所示,50 個(gè)節(jié)點(diǎn)隨機(jī)分布在1000m×1000m的矩形范圍內(nèi),節(jié)點(diǎn)通信半徑為250m,節(jié)點(diǎn)采取隨機(jī)點(diǎn)移動(dòng)模型,移動(dòng)速度15m/s?!鞍f交率”定義為網(wǎng)絡(luò)中收到數(shù)據(jù)包的節(jié)點(diǎn)數(shù)占全部節(jié)點(diǎn)數(shù)的比率。改變廣播概率p并統(tǒng)計(jì)包遞交率,結(jié)果如圖3 所示,可見當(dāng)廣播概率達(dá)到0.6 時(shí),包遞交率已經(jīng)超過90%,這被稱為相變現(xiàn)象[9],說明當(dāng)廣播概率達(dá)到某個(gè)門限值之后進(jìn)一步增加概率已經(jīng)沒有太大增益,反而無謂地消耗網(wǎng)絡(luò)資源。
圖2 應(yīng)急通信網(wǎng)
圖3 應(yīng)急通信網(wǎng)的概率泛洪
應(yīng)急通信網(wǎng)的包遞交率反映了網(wǎng)絡(luò)可靠性,高的包遞交率意味著網(wǎng)絡(luò)中大部分節(jié)點(diǎn)都收到了數(shù)據(jù)包。然而,高的包遞交率需要高的廣播概率支撐,后者會(huì)產(chǎn)生大量的中繼轉(zhuǎn)發(fā)和數(shù)據(jù)包副本,造成大量的信號(hào)沖突和信道浪費(fèi),因此降低了網(wǎng)絡(luò)有效性。可見,網(wǎng)絡(luò)的可靠性和有效性是一對(duì)矛盾,為了實(shí)現(xiàn)二者的折中,對(duì)于不同的應(yīng)用需求提供個(gè)性化服務(wù),本文提出一種加權(quán)概率廣播算法,具體參照下面的目標(biāo)函數(shù)。
其中,α,β,γ取值均介于(0,1)之間。β等于轉(zhuǎn)發(fā)數(shù)據(jù)包的節(jié)點(diǎn)數(shù)與收到數(shù)據(jù)包的節(jié)點(diǎn)數(shù)的比值,稱之為包傳輸?shù)臍w一化代價(jià)函數(shù)。在收到數(shù)據(jù)包節(jié)點(diǎn)數(shù)相同的條件下,參與轉(zhuǎn)發(fā)數(shù)據(jù)包的節(jié)點(diǎn)數(shù)越少,信道資源消耗就越少,有效性就越高,因此β描述了網(wǎng)絡(luò)的有效性,β越小則有效性越高。γ代表包丟失率(即1-γ代表包遞交率),1-γ定義為收到數(shù)據(jù)包的節(jié)點(diǎn)數(shù)占總節(jié)點(diǎn)數(shù)的比值,可見1-γ描述了網(wǎng)絡(luò)的可靠性,1-γ越大則網(wǎng)絡(luò)越可靠。α表示在有效性和可靠性之間折中的加權(quán)系數(shù),高的α代表高有效性和低可靠性,低的α代表低有效性和高可靠性。最后,T是目標(biāo)函數(shù),代表綜合考慮可靠性和有效性之后的總的資源消耗,對(duì)于具體應(yīng)用場(chǎng)景,總是希望β和γ盡可能地小,因此對(duì)于一定的節(jié)點(diǎn)度k,應(yīng)該確定廣播概率p以使得T盡可能小,稱這個(gè)概率p為對(duì)應(yīng)于該應(yīng)用場(chǎng)景的最優(yōu)廣播概率。
基于實(shí)驗(yàn)2 的仿真設(shè)置,采用5 個(gè)加權(quán)系數(shù)α,得到廣播概率p和目標(biāo)函數(shù)T的關(guān)系,如圖4所示。每條曲線對(duì)應(yīng)于一個(gè)加權(quán)系數(shù),每條曲線的最低點(diǎn)是所尋找的最優(yōu)廣播概率。
圖4 目標(biāo)函數(shù)T(n=50,k=8.817)
類似于實(shí)驗(yàn)2 的仿真設(shè)置,通過改變節(jié)點(diǎn)數(shù)n(對(duì)應(yīng)于改變節(jié)點(diǎn)度k),通過一系列實(shí)驗(yàn)可以得到不同的網(wǎng)絡(luò)配置下最優(yōu)廣播概率的取值,如表1所示。
表1 不同網(wǎng)絡(luò)配置下廣播概率最優(yōu)解
實(shí)際應(yīng)用中,對(duì)于表1 中沒有列出的網(wǎng)絡(luò)參數(shù)配置,可以采用平均估值的方法得到最優(yōu)概率。比如對(duì)于k=12,α=0.2,可以估計(jì)出p=0.66。進(jìn)一步,基于這組參數(shù)通過仿真實(shí)驗(yàn)可以對(duì)概率廣播和普通廣播(相當(dāng)于p=1 的概率廣播)進(jìn)行性能比較。實(shí)驗(yàn)結(jié)果如圖5 和圖6 所示??梢?,通過使用加權(quán)系數(shù)α,概率廣播的歸一化代價(jià)函數(shù)減少了大約40%,而損失的包遞交率僅僅不到10%。
圖5 兩種廣播算法包遞交率的比較
圖6 兩種廣播算法歸一化代價(jià)函數(shù)的比較
針對(duì)應(yīng)急通信網(wǎng)絡(luò),在分析網(wǎng)絡(luò)連通性和節(jié)點(diǎn)度之間關(guān)系的基礎(chǔ)上,本文提出了一種加權(quán)的概率廣播算法,該算法通過設(shè)置加權(quán)因子α和目標(biāo)函數(shù)T,在網(wǎng)絡(luò)通信的有效性和可靠性之間進(jìn)行折中,以滿足不同網(wǎng)絡(luò)規(guī)模和應(yīng)用場(chǎng)景的具體需求。應(yīng)用該加權(quán)概率廣播算法,根據(jù)網(wǎng)絡(luò)規(guī)模和節(jié)點(diǎn)平均度,通過仿真實(shí)驗(yàn)可以得到最優(yōu)廣播概率p,然后以該最優(yōu)廣播概率進(jìn)行概率廣播。仿真實(shí)驗(yàn)表明,通過使用該算法確定的最優(yōu)廣播概率可以以很小的包遞交率損失換取很大的網(wǎng)絡(luò)廣播歸一化代價(jià)的增益,從而獲得極大的有效性提升。