一種應(yīng)急通信網(wǎng)加權(quán)廣播算法＊

秦 娜，劉宴濤

(1.嘉應(yīng)學(xué)院計算機學(xué)院，廣東 梅州 514015；2.蒙古研究大學(xué))

0 引言

無線自組織網(wǎng)絡(luò)，簡稱無線自組網(wǎng)（Ad hoc Network），又稱移動自組網(wǎng)（MANET-Mobile Ad hoc Network），是一種特殊的無線網(wǎng)絡(luò)形式。這種網(wǎng)絡(luò)為某種特殊應(yīng)用或特殊目的而構(gòu)建，由一組帶有無線收發(fā)信機的移動終端組成，網(wǎng)絡(luò)節(jié)點同時充當終端主機和路由器的角色，結(jié)合了計算機網(wǎng)絡(luò)和無線通信的優(yōu)勢，具有無中心、自組織、多跳路由、動態(tài)拓撲、快速布設(shè)、不依賴基礎(chǔ)設(shè)施、體積小、能耗低、分布式、合作通信、高抗毀、可移動、可重組等特點。無線自組網(wǎng)與傳感器網(wǎng)絡(luò)、物聯(lián)網(wǎng)等無線網(wǎng)絡(luò)技術(shù)具有密切的聯(lián)系，其主要應(yīng)用場合有搶險救災(zāi)、戰(zhàn)場通信、野外救援、會議慶典、水庫、礦山、公安、消防、森林防火和公共交通等。

應(yīng)急通信網(wǎng)絡(luò)是無線自組網(wǎng)在民用領(lǐng)域的一種典型應(yīng)用，這種網(wǎng)絡(luò)主要應(yīng)用于地震、洪水、泥石流等災(zāi)難之后臨時創(chuàng)建應(yīng)急通信保障。以地震為例，災(zāi)害過后由于電力、通信等基礎(chǔ)設(shè)施損毀殆盡，災(zāi)難現(xiàn)場的情況無法及時為外界獲知，給快速有效的施救造成了極大的困難。地震過后搶救生命意味著與時間賽跑，如果震后超過了72 小時，人員生還的希望就很渺茫，所以快速準確地采集到震區(qū)的實時情況（比如人體紅外、聲音、圖像、視頻、生命體征等）是災(zāi)難救助的首要任務(wù)。這就把不依賴于基礎(chǔ)設(shè)施、快速、自動的通信保障的重要性提到了前所未有的高度，而無線自組網(wǎng)正好符合了這一要求。

應(yīng)急通信網(wǎng)絡(luò)的研究重點包括寬帶無線接入、單/組/廣播路由算法、網(wǎng)絡(luò)的覆蓋性和連通性、移動性管理、功率控制等等?？凳匦臶1]針對礦井下多點應(yīng)急救援研究了基于無線Mesh網(wǎng)絡(luò)的應(yīng)急通信基站，提出了應(yīng)急通信基站無線中繼與無線覆蓋的方案，并對應(yīng)急通信基站的最大傳輸距離進行了模擬仿真。王魯寧[2]提出了系統(tǒng)化、扁平化、智能化的感知網(wǎng)絡(luò)全覆蓋的現(xiàn)代應(yīng)急管理體系的建設(shè)思路。賀燦輝[3]結(jié)合消防應(yīng)急通信構(gòu)建Mesh 網(wǎng)絡(luò)以提高消防應(yīng)急的質(zhì)量和安全性。肖強[4]對應(yīng)急通信技術(shù)的發(fā)展、特點和趨勢進行綜述。周雄偉[5]通過對應(yīng)急通信和公共通信的特點比較，提出了應(yīng)急通信的服務(wù)保障模式，并對應(yīng)急通信標準規(guī)范給出建議。姜海涵[6]針對信道吞吐量低、阻塞率高等問題，提出了應(yīng)急通信異構(gòu)網(wǎng)絡(luò)的信道選擇方法。張昊曄[7]基于認知無線電技術(shù)，提出了不同任務(wù)策略下的優(yōu)化目標和約束條件，實現(xiàn)網(wǎng)絡(luò)效能最大化。

可靠性和有效性是應(yīng)急通信網(wǎng)的兩項重要指標，前者表示信源發(fā)出的數(shù)據(jù)包能準確可靠地為所有信宿接收，后者表示網(wǎng)絡(luò)的傳輸速率快、資源消耗少。然而在實際應(yīng)用中這兩者往往是一對矛盾，為了提高可靠性，需要增加節(jié)點轉(zhuǎn)發(fā)概率，減少丟包率，而這又不可避免地加劇信號沖突和信道資源占用，降低有效性。為了調(diào)和這兩者的矛盾，本文提出了一種加權(quán)的概率廣播算法，通過引入加權(quán)系數(shù)和目標函數(shù)取得有效性和可靠性的折中。

本文的后續(xù)如下：第1 節(jié)通過仿真實驗測算節(jié)點度和網(wǎng)絡(luò)連通度的關(guān)系，為概率廣播實驗的節(jié)點密度提供定量依據(jù)；第2 節(jié)介紹概率廣播的基本原理并解釋相變現(xiàn)象；第3節(jié)提出了加權(quán)的概率廣播算法，通過引入加權(quán)系數(shù)和目標函數(shù)在有效性和可靠性之間進行折中，通過大量仿真實驗測算最優(yōu)廣播概率，并通過仿真實驗來對比加權(quán)概率廣播和普通廣播；第4 節(jié)給出本文的結(jié)論。

1 應(yīng)急通信網(wǎng)絡(luò)的連通性

連通性是應(yīng)急通信網(wǎng)絡(luò)的重要指標，所有路由算法的有效性都是以網(wǎng)絡(luò)連通為前提的。影響網(wǎng)絡(luò)連通性的因素有很多，如網(wǎng)絡(luò)的拓撲和覆蓋范圍，節(jié)點的數(shù)目和通信半徑，對于移動網(wǎng)絡(luò)還包括節(jié)點的移動性。因此，很難對網(wǎng)絡(luò)連通性做出精確的理論分析。本節(jié)應(yīng)用Ad hoc 網(wǎng)絡(luò)仿真工具箱ANSim，對網(wǎng)絡(luò)連通性做仿真研究。

網(wǎng)絡(luò)連通概率與網(wǎng)絡(luò)平均度有關(guān)。節(jié)點u的度是指與u直接相連的節(jié)點數(shù)目，全部節(jié)點度的平均值稱為網(wǎng)絡(luò)的平均度。假設(shè)網(wǎng)絡(luò)覆蓋面積為S，節(jié)點的通信半徑為R，節(jié)點數(shù)目為n，則網(wǎng)絡(luò)平均度由式⑴決定。

仿真實驗1：n個節(jié)點均勻分布在1000m×1000m的矩形范圍內(nèi)，節(jié)點通信半徑為250m，節(jié)點采取隨機點移動模型。通過調(diào)整n的值并通過公式⑴計算得到一組平均度k的值，應(yīng)用ANSim 的統(tǒng)計功能可以得到網(wǎng)絡(luò)連通概率（即網(wǎng)絡(luò)最大連通組中節(jié)點數(shù)占全部節(jié)點數(shù)的比例）和平均度k的關(guān)系曲線，如圖1 所示。由此可見，網(wǎng)絡(luò)連通概率隨著節(jié)點度的增加而提高，當節(jié)點度達到6 時，網(wǎng)絡(luò)連通概率已超過95%，表現(xiàn)出很健壯的連通性。

圖1 網(wǎng)絡(luò)連通概率和節(jié)點平均度的關(guān)系

2 概率廣播算法

泛洪廣播，簡稱泛洪，是一種廣播路由技術(shù)，是指數(shù)據(jù)包從源節(jié)點發(fā)出后，所有收到該數(shù)據(jù)包的中間節(jié)點對其進行中繼轉(zhuǎn)發(fā)，一級一級地向后傳遞，像洪水泛濫一樣，直到所有節(jié)點都收到該數(shù)據(jù)包為止。泛洪可以單獨作為路由算法使用，也可以輔助其他路由算法，比如動態(tài)源路由DSR(Dynamic Source Routing)、按需組播路由協(xié)議ODMRP(OnDemand Multicast Routing Proto-col)，用于這些路由的建立與更新。

普通的泛洪廣播算法中，中間節(jié)點以概率1 轉(zhuǎn)發(fā)數(shù)據(jù)包，網(wǎng)絡(luò)中會出現(xiàn)大量的數(shù)據(jù)包，造成劇烈的信號沖突和信道浪費。概率廣播[8]可以緩解這一問題，所謂概率廣播是指中間節(jié)點收到上游節(jié)點發(fā)來的數(shù)據(jù)包后以概率p轉(zhuǎn)發(fā)該數(shù)據(jù)包。下面基于OPNET 設(shè)計一組仿真實驗驗證泛洪概率p對于廣播算法的影響。

仿真實驗2：如圖2 所示，50 個節(jié)點隨機分布在1000m×1000m的矩形范圍內(nèi)，節(jié)點通信半徑為250m，節(jié)點采取隨機點移動模型，移動速度15m/s?！鞍f交率”定義為網(wǎng)絡(luò)中收到數(shù)據(jù)包的節(jié)點數(shù)占全部節(jié)點數(shù)的比率。改變廣播概率p并統(tǒng)計包遞交率，結(jié)果如圖3 所示，可見當廣播概率達到0.6 時，包遞交率已經(jīng)超過90%，這被稱為相變現(xiàn)象[9]，說明當廣播概率達到某個門限值之后進一步增加概率已經(jīng)沒有太大增益，反而無謂地消耗網(wǎng)絡(luò)資源。

圖2 應(yīng)急通信網(wǎng)

圖3 應(yīng)急通信網(wǎng)的概率泛洪

3 針對應(yīng)急通信網(wǎng)的加權(quán)概率廣播

應(yīng)急通信網(wǎng)的包遞交率反映了網(wǎng)絡(luò)可靠性，高的包遞交率意味著網(wǎng)絡(luò)中大部分節(jié)點都收到了數(shù)據(jù)包。然而，高的包遞交率需要高的廣播概率支撐，后者會產(chǎn)生大量的中繼轉(zhuǎn)發(fā)和數(shù)據(jù)包副本，造成大量的信號沖突和信道浪費，因此降低了網(wǎng)絡(luò)有效性?？梢?，網(wǎng)絡(luò)的可靠性和有效性是一對矛盾，為了實現(xiàn)二者的折中，對于不同的應(yīng)用需求提供個性化服務(wù)，本文提出一種加權(quán)概率廣播算法，具體參照下面的目標函數(shù)。

其中，α，β，γ取值均介于(0,1)之間。β等于轉(zhuǎn)發(fā)數(shù)據(jù)包的節(jié)點數(shù)與收到數(shù)據(jù)包的節(jié)點數(shù)的比值，稱之為包傳輸?shù)臍w一化代價函數(shù)。在收到數(shù)據(jù)包節(jié)點數(shù)相同的條件下，參與轉(zhuǎn)發(fā)數(shù)據(jù)包的節(jié)點數(shù)越少，信道資源消耗就越少，有效性就越高，因此β描述了網(wǎng)絡(luò)的有效性，β越小則有效性越高。γ代表包丟失率（即1-γ代表包遞交率），1-γ定義為收到數(shù)據(jù)包的節(jié)點數(shù)占總節(jié)點數(shù)的比值，可見1-γ描述了網(wǎng)絡(luò)的可靠性，1-γ越大則網(wǎng)絡(luò)越可靠。α表示在有效性和可靠性之間折中的加權(quán)系數(shù)，高的α代表高有效性和低可靠性，低的α代表低有效性和高可靠性。最后，T是目標函數(shù)，代表綜合考慮可靠性和有效性之后的總的資源消耗，對于具體應(yīng)用場景，總是希望β和γ盡可能地小，因此對于一定的節(jié)點度k，應(yīng)該確定廣播概率p以使得T盡可能小，稱這個概率p為對應(yīng)于該應(yīng)用場景的最優(yōu)廣播概率。

基于實驗2 的仿真設(shè)置，采用5 個加權(quán)系數(shù)α，得到廣播概率p和目標函數(shù)T的關(guān)系，如圖4所示。每條曲線對應(yīng)于一個加權(quán)系數(shù)，每條曲線的最低點是所尋找的最優(yōu)廣播概率。

圖4 目標函數(shù)T（n=50,k=8.817）

類似于實驗2 的仿真設(shè)置，通過改變節(jié)點數(shù)n（對應(yīng)于改變節(jié)點度k），通過一系列實驗可以得到不同的網(wǎng)絡(luò)配置下最優(yōu)廣播概率的取值，如表1所示。

表1 不同網(wǎng)絡(luò)配置下廣播概率最優(yōu)解

實際應(yīng)用中，對于表1 中沒有列出的網(wǎng)絡(luò)參數(shù)配置，可以采用平均估值的方法得到最優(yōu)概率。比如對于k=12，α=0.2，可以估計出p=0.66。進一步，基于這組參數(shù)通過仿真實驗可以對概率廣播和普通廣播（相當于p=1 的概率廣播）進行性能比較。實驗結(jié)果如圖5 和圖6 所示?？梢?，通過使用加權(quán)系數(shù)α，概率廣播的歸一化代價函數(shù)減少了大約40%，而損失的包遞交率僅僅不到10%。

圖5 兩種廣播算法包遞交率的比較

圖6 兩種廣播算法歸一化代價函數(shù)的比較

4 結(jié)論

針對應(yīng)急通信網(wǎng)絡(luò)，在分析網(wǎng)絡(luò)連通性和節(jié)點度之間關(guān)系的基礎(chǔ)上，本文提出了一種加權(quán)的概率廣播算法，該算法通過設(shè)置加權(quán)因子α和目標函數(shù)T，在網(wǎng)絡(luò)通信的有效性和可靠性之間進行折中，以滿足不同網(wǎng)絡(luò)規(guī)模和應(yīng)用場景的具體需求。應(yīng)用該加權(quán)概率廣播算法，根據(jù)網(wǎng)絡(luò)規(guī)模和節(jié)點平均度，通過仿真實驗可以得到最優(yōu)廣播概率p，然后以該最優(yōu)廣播概率進行概率廣播。仿真實驗表明，通過使用該算法確定的最優(yōu)廣播概率可以以很小的包遞交率損失換取很大的網(wǎng)絡(luò)廣播歸一化代價的增益，從而獲得極大的有效性提升。