基于鄰居覆蓋信息和節(jié)點(diǎn)移動(dòng)速度的無線自組網(wǎng)多播方案

魯頂柱 高靜 董守斌

摘 ?要： 針對(duì)無線自組網(wǎng)節(jié)點(diǎn)的移動(dòng)導(dǎo)致多播可靠性降低、開銷和時(shí)延增加的問題，提出基于鄰居覆蓋信息的多播方案。該方案通過少量的Hello報(bào)文收集一跳內(nèi)的鄰居信息，并據(jù)此實(shí)時(shí)計(jì)算節(jié)點(diǎn)的密度系數(shù)、鄰居節(jié)點(diǎn)未覆蓋率等參數(shù)，利用所獲參數(shù)動(dòng)態(tài)調(diào)整節(jié)點(diǎn)的多播數(shù)據(jù)轉(zhuǎn)發(fā)時(shí)延與轉(zhuǎn)發(fā)概率。為進(jìn)一步降低時(shí)延，提出一種基于節(jié)點(diǎn)移動(dòng)速度的數(shù)據(jù)分發(fā)方案，它允許部分快速移動(dòng)節(jié)點(diǎn)采用更高的概率轉(zhuǎn)發(fā)多播數(shù)據(jù)。將其擴(kuò)展至多播方案中，形成基于鄰居覆蓋信息和節(jié)點(diǎn)移動(dòng)速度的多播方案。NS2的仿真結(jié)果表明，與現(xiàn)有方案相比，該方案將分組投遞率提高27%，控制開銷減少33.2%，并將端到端平均時(shí)延降低45%。

關(guān)鍵詞： 多播方案; 無線自組網(wǎng); 鄰居覆蓋信息; 轉(zhuǎn)發(fā)時(shí)延; 分組投遞率; 端到端平均時(shí)遲

中圖分類號(hào)： TN915?34; TP393.04 ? ? ? ? ? ? ?文獻(xiàn)標(biāo)識(shí)碼： A ? ? ? ? ? ? ? ? ? ?文章編號(hào)： 1004?373X（2019）10?0053?07

A wireless ad hoc network multicast scheme based on neighbor coverage

information and node motion velocity

LU Dingzhu1，2， GAO Jing1， DONG Shoubin2

（1. School of Information & Engineering， The Open University of Guangdong， Guangzhou 510091， China;

2. School of Computer Science & Engineering， South China University of Technology， Guangzhou 510006， China）

Abstract： A multicast scheme based on neighbor coverage information is proposed to solve the problems of multicast reliability decrease， overhead increase and latency increase caused by node mobility in wireless ad hoc networks. In the scheme， the one?hop neighbor information is collected by using a few Hello messages， and accordingly， parameters such as node density coefficient， and uncoverage rate of neighbor nodes are calculated in real time. The obtained parameters are used to dynamically adjust the forwarding time delay and forwarding probability of nodes′ multicast data. A data distribution scheme based on node motion velocity is proposed to further reduce the time delay. The scheme allows part of fast mobile nodes to perform multicast data transmission with a higher probability. A multicast scheme based on neighbor coverage information and node motion velocity is formed by extending the data distribution scheme to the multicast scheme. The results of the simulation with the NS2 show that the proposed scheme can improve the packet delivery rate by 27%， and decrease the control overhead by 33.2% and the average end?to?end delay by 45% in comparison with the existing schemes.

Keywords： multicast scheme; ad hoc network; neighbor coverage information; forwarding delay; packet delivery rate; end?to?end average delay

0 ?引 ?言

無線自組網(wǎng)的多播方案按拓?fù)浣Y(jié)構(gòu)可分為三類[1]：基于樹結(jié)構(gòu)的、基于網(wǎng)格結(jié)構(gòu)的和無狀態(tài)的多播方案?；跇浣Y(jié)構(gòu)的方案[2?5]利用分發(fā)樹轉(zhuǎn)發(fā)數(shù)據(jù)，同一數(shù)據(jù)只會(huì)向成員節(jié)點(diǎn)分發(fā)一次，數(shù)據(jù)傳輸效率高;但在無線自組網(wǎng)中樹結(jié)構(gòu)易被節(jié)點(diǎn)的移動(dòng)所破壞，難于維護(hù)，可靠性低，只適合在節(jié)點(diǎn)低速移動(dòng)的環(huán)境中應(yīng)用。

基于網(wǎng)格結(jié)構(gòu)的方案[6?8]提供冗余的路徑，彌補(bǔ)了樹結(jié)構(gòu)的不足;但冗余路徑維護(hù)開銷大，同時(shí)易引發(fā)沖突，增加傳輸開銷。與基于樹結(jié)構(gòu)的方案相比，基于網(wǎng)格結(jié)構(gòu)的多播方案對(duì)節(jié)點(diǎn)移動(dòng)的適應(yīng)能力更強(qiáng)[9]。

無狀態(tài)方案 [10?11]采用源路由或以受限的泛洪方式轉(zhuǎn)發(fā)數(shù)據(jù)，不需要維護(hù)拓?fù)?，減少了開銷，對(duì)節(jié)點(diǎn)移動(dòng)的適應(yīng)能力最強(qiáng)。本文提出基于鄰居覆蓋信息和節(jié)點(diǎn)移動(dòng)速度的多播方案（a Neighbor Coverage and Velocity?based Multicast Scheme，NCVM）。該方案根據(jù)一跳鄰居的多播數(shù)據(jù)未覆蓋信息和自身的移動(dòng)速度來自適應(yīng)的動(dòng)態(tài)改變多播數(shù)據(jù)的轉(zhuǎn)發(fā)概率與轉(zhuǎn)發(fā)時(shí)延，以獲得較小的端到端時(shí)延和通信開銷良好的分組投遞率。

1 ?基于鄰居覆蓋信息的多播方案

將網(wǎng)絡(luò)用一個(gè)無向圖[ G=V， E ]來表示，其中V是網(wǎng)絡(luò)中所有節(jié)點(diǎn)的集合，E是網(wǎng)絡(luò)中所有無向邊的集合，節(jié)點(diǎn)之間的每一條鏈路都用一條無向邊來表示。節(jié)點(diǎn)ni的鄰居節(jié)點(diǎn)集合[Nni] 定義為：

[nini，nj∈E&ni，nj∈V]

[Nni]表示鄰居節(jié)點(diǎn)集合中節(jié)點(diǎn)的數(shù)量。

1.1 ?成員關(guān)系維護(hù)

在基于鄰居覆蓋信息的移動(dòng)自組網(wǎng)多播方案（a Neighbor Coverage?based Multicast Scheme，NCM）中，每個(gè)多播組成員僅需維護(hù)一跳內(nèi)的成員關(guān)系。因而在節(jié)點(diǎn)頻繁移動(dòng)的情況下也能通過Hello報(bào)文及時(shí)更新成員關(guān)系，并保持較小的維護(hù)開銷，特別適合于移動(dòng)場(chǎng)景。成員關(guān)系維護(hù)具體過程如下：

當(dāng)多播源節(jié)點(diǎn)r需要發(fā)送數(shù)據(jù)時(shí)，它首先向全網(wǎng)廣播一個(gè)JOIN_GROUP報(bào)文，其中包含了多播組標(biāo)識(shí)字段GROUP_ID。當(dāng)多播接收節(jié)點(diǎn)ni收到JOIN_GROUP報(bào)文后，該節(jié)點(diǎn)構(gòu)造一個(gè)Hello報(bào)文，并且向自己的鄰居廣播這個(gè)Hello報(bào)文。Hello報(bào)文中包含了以下字段：

1） ID（ni）。發(fā)送節(jié)點(diǎn)ni的ID。

2） Group_ID。Group_ID是發(fā)送節(jié)點(diǎn)所加入的多播組ID。

3） N（ni）。N（ni）中包含了ni節(jié)點(diǎn)的所有鄰居多播組成員節(jié)點(diǎn)ID，稱為鄰居節(jié)點(diǎn)集合。

4） LEAF_FLAG。如果節(jié)點(diǎn)ni是一個(gè)葉子節(jié)點(diǎn)，LEAF_FLAG位被置為1，否則Hello報(bào)文中不包括該字段。

定義1 葉子節(jié)點(diǎn)：如果某個(gè)節(jié)點(diǎn)僅有一個(gè)鄰居節(jié)點(diǎn)，那么這個(gè)節(jié)點(diǎn)是葉子節(jié)點(diǎn)，LEAF_FLAG位被置為1。

定義2 次葉子節(jié)點(diǎn)：如果節(jié)點(diǎn)的鄰居節(jié)點(diǎn)中有葉子節(jié)點(diǎn)，那么這個(gè)節(jié)點(diǎn)是次葉子節(jié)點(diǎn)。

在成員關(guān)系初始化完成之后，每個(gè)節(jié)點(diǎn)周期性地交換Hello報(bào)文來更新成員信息。如果一個(gè)節(jié)點(diǎn)在Hello報(bào)文交換周期內(nèi)未收到鄰居成員節(jié)點(diǎn)的Hello報(bào)文，將從鄰居節(jié)點(diǎn)集合中移除該鄰居節(jié)點(diǎn)。離開多播組的節(jié)點(diǎn)不需要發(fā)送任何消息。

為了減少Hello報(bào)文帶來的控制開銷，多播方案采用了捎帶技術(shù)，利用多播報(bào)文捎帶Hello報(bào)文。只有當(dāng)多播報(bào)文的發(fā)送間隔大于Hello報(bào)文交換周期時(shí)才需要單獨(dú)發(fā)送Hello報(bào)文。

1.2 ?未覆蓋鄰居節(jié)點(diǎn)集合

鄰居節(jié)點(diǎn)集合與未覆蓋鄰居節(jié)點(diǎn)集合如圖1所示，節(jié)點(diǎn)[ni]與上游節(jié)點(diǎn)r相鄰，并收到來自r的多播數(shù)據(jù)m。[N（ni）]和N（r）分別是節(jié)點(diǎn)[ni]與上游節(jié)點(diǎn)r的鄰居節(jié)點(diǎn)集合，也就是以各自為圓心，以信號(hào)覆蓋范圍為半徑的圓中所有成員節(jié)點(diǎn)（自己除外）構(gòu)成的集合。由于無線網(wǎng)絡(luò)的廣播特性，節(jié)點(diǎn)[ni]與節(jié)點(diǎn)r共同的鄰居節(jié)點(diǎn)會(huì)收到來自r的多播數(shù)據(jù)m，節(jié)點(diǎn)[ni]的另外一部分非共同鄰居節(jié)點(diǎn)卻未能收到多播數(shù)據(jù)m，這部分節(jié)點(diǎn)（圖1最右邊區(qū)域?qū)嵭墓?jié)點(diǎn)）組成了[ni]的未覆蓋鄰居節(jié)點(diǎn)集合[U（ni）]，定義如下：

[U（ni）=N（ni）-[N（ni）?N（r）]-{r}] ? ? （1）

多播轉(zhuǎn)發(fā)時(shí)延：節(jié)點(diǎn)在第一次收一個(gè)多播數(shù)據(jù)后需要等待一段時(shí)間，之后才根據(jù)自己的鄰居節(jié)點(diǎn)多播數(shù)據(jù)覆蓋情況決定是否轉(zhuǎn)發(fā)這個(gè)多播數(shù)據(jù)，這個(gè)等待時(shí)間稱為多播轉(zhuǎn)發(fā)時(shí)延。

圖1 ?鄰居節(jié)點(diǎn)集合與未覆蓋鄰居節(jié)點(diǎn)集合

合理的選擇多播轉(zhuǎn)發(fā)時(shí)延非常重要，因?yàn)椋?/p>

1） r的部分鄰居節(jié)點(diǎn)在彼此的信號(hào)覆蓋范圍之內(nèi)（圖1公共區(qū)域空心節(jié)點(diǎn)），這些鄰居節(jié)點(diǎn)在收到多播數(shù)據(jù)后如果同時(shí)轉(zhuǎn)發(fā)該數(shù)據(jù)就會(huì)引起沖突，節(jié)點(diǎn)通過等待一個(gè)時(shí)延可以減少?zèng)_突。

2） 節(jié)點(diǎn)[ni]在等待時(shí)延的過程中可能會(huì)收到來自r以外的其他鄰居節(jié)點(diǎn)轉(zhuǎn)發(fā)的重復(fù)多播數(shù)據(jù)，那么[U（ni）]可能會(huì)減小，轉(zhuǎn)發(fā)概率也會(huì)隨之減小。

如果節(jié)點(diǎn)[ni]在多播轉(zhuǎn)發(fā)時(shí)延結(jié)束之前收到鄰居節(jié)點(diǎn)[nj]轉(zhuǎn)發(fā)的多播數(shù)據(jù)m，那么節(jié)點(diǎn)ni需要根據(jù)節(jié)點(diǎn)nj的鄰居節(jié)點(diǎn)集合來重新計(jì)算自己的未覆蓋鄰居節(jié)點(diǎn)集合[U（ni）]，計(jì)算公式如下：

[Uni=Uni-[Uni?Nni]-{nj}] （2）

1.3 ?多播數(shù)據(jù)轉(zhuǎn)發(fā)概率

節(jié)點(diǎn)[ni]是否轉(zhuǎn)發(fā)來自上游節(jié)點(diǎn)r的多播數(shù)據(jù)受到多個(gè)因素影響：

1） 節(jié)點(diǎn)[ni]的鄰居節(jié)點(diǎn)數(shù)。[ni]的鄰居節(jié)點(diǎn)數(shù)較多時(shí)，為了避免產(chǎn)生過多的重復(fù)數(shù)據(jù)，多播數(shù)據(jù)轉(zhuǎn)發(fā)概率應(yīng)該稍小;反之，應(yīng)取較大的概率。

2） 節(jié)點(diǎn)[ni]的鄰居節(jié)點(diǎn)未覆蓋率和未覆蓋鄰居絕對(duì)數(shù)量。對(duì)于節(jié)點(diǎn)[ni]而言，其鄰居節(jié)點(diǎn)未覆蓋率越大，轉(zhuǎn)發(fā)多播數(shù)據(jù)所獲得的覆蓋率就越大;如果節(jié)點(diǎn)[ni]鄰居未覆蓋率較小，但其未覆蓋鄰居絕對(duì)數(shù)量較大時(shí)，轉(zhuǎn)發(fā)多播數(shù)據(jù)也同樣是值得的。

鄰居節(jié)點(diǎn)數(shù)量與未覆蓋鄰居絕對(duì)數(shù)量影響。文獻(xiàn)[12]研究得出：當(dāng)每個(gè)節(jié)點(diǎn)的鄰居多于5.177 4log N（記為Nc，其中N為網(wǎng)絡(luò)中節(jié)點(diǎn)總數(shù)）時(shí)，這個(gè)網(wǎng)絡(luò)漸近趨于連通。本文將引入5.177 4log N來衡量節(jié)點(diǎn)ni的鄰居數(shù)和未覆蓋鄰居絕對(duì)數(shù)量的多少，以決定多播數(shù)據(jù)轉(zhuǎn)發(fā)概率的大小。

將[Nni] 與Nc之比定義為密度系數(shù)d（ni）。[Nni]值越大，密度系數(shù)d（ni）越大，網(wǎng)絡(luò)連通性越好，節(jié)點(diǎn)ni的多播數(shù)據(jù)轉(zhuǎn)發(fā)概率就應(yīng)該越小，產(chǎn)生的冗余和沖突也就越少。

[d（ni）=NniNc] ? （3）

同樣用 [Uni]與Nc之比來衡量未覆蓋鄰居絕對(duì)數(shù)量大小，定義為未覆蓋鄰居數(shù)影響因子Fu（ni）。當(dāng)未覆蓋鄰居數(shù)影響因子越大時(shí)，轉(zhuǎn)發(fā)多播數(shù)據(jù)有效覆蓋的鄰居節(jié)點(diǎn)也就越多，轉(zhuǎn)發(fā)效率越高，帶寬的利用率越高。

[Funi=UniNc] ?（4）

鄰居節(jié)點(diǎn)未覆蓋率影響。當(dāng)轉(zhuǎn)發(fā)時(shí)延結(jié)束時(shí)，節(jié)點(diǎn)ni需要計(jì)算鄰居節(jié)點(diǎn)未覆蓋率[Ru（ni）]：

[Ru（ni）=UniNni-1] ?（5）

式中：[·]表示集合中成員的數(shù)量;[Nni-1]表示在節(jié)點(diǎn)ni的未覆蓋鄰居節(jié)點(diǎn)集合中剔除了節(jié)點(diǎn)r。

當(dāng)節(jié)點(diǎn)ni的鄰居節(jié)點(diǎn)未覆蓋率較大時(shí)，節(jié)點(diǎn)ni應(yīng)當(dāng)以較大的概率轉(zhuǎn)發(fā)接收到的多播數(shù)據(jù)，以提高帶寬利用率;相反，當(dāng)節(jié)點(diǎn)ni的鄰居節(jié)點(diǎn)未覆蓋率較小時(shí)，應(yīng)當(dāng)在保證分組投遞率的前提下以盡可能小的概率轉(zhuǎn)發(fā)多播數(shù)據(jù)，以減少冗余和沖突。

多播數(shù)據(jù)轉(zhuǎn)發(fā)概率計(jì)算。綜合節(jié)點(diǎn)ni的鄰居節(jié)點(diǎn)數(shù)、鄰居節(jié)點(diǎn)未覆蓋率和未覆蓋鄰居節(jié)點(diǎn)絕對(duì)數(shù)量的影響得出基于鄰居信息的多播數(shù)據(jù)轉(zhuǎn)發(fā)概率pk（ni）：

[pk（ni）=β·Ru（ni）+（1-β）·Fu（ni）d（ni）] ? （6）

式中，β和[（1-β）]分別是鄰居節(jié)點(diǎn)未覆蓋率和未覆蓋鄰居數(shù)影響因子對(duì)多播數(shù)據(jù)轉(zhuǎn)發(fā)概率的影響系數(shù)。如果pk（ni）>1時(shí)，pk（ni）取值為1。

為了保證多播分組投遞率，當(dāng)ni節(jié)點(diǎn)的鄰居中有葉子節(jié)點(diǎn)nj時(shí)，如圖1所示，即ni節(jié)點(diǎn)是次葉子節(jié)點(diǎn)時(shí)，ni節(jié)點(diǎn)將以概率1轉(zhuǎn)發(fā)所接收到的多播數(shù)據(jù)，pk（ni）的取值為1。為了減少冗余數(shù)據(jù)，作為轉(zhuǎn)發(fā)路徑盡頭的葉子在接收到多播數(shù)據(jù)后，不再對(duì)其進(jìn)行轉(zhuǎn)發(fā)，p（nj）的取值為0。

因此，節(jié)點(diǎn)的多播數(shù)據(jù)的轉(zhuǎn)發(fā)概率為：

[pkni=0， ? ? ?Uni=?1， ? ? ? ?nj，nj∈Uni&Nnj={ni}min1，β·Runi+1-β·Funidni，其他] ? ? （7）

1.4 ?多播轉(zhuǎn)發(fā)時(shí)延計(jì)算

合理設(shè)置轉(zhuǎn)發(fā)時(shí)延不僅能錯(cuò)開相鄰節(jié)點(diǎn)的多播數(shù)據(jù)轉(zhuǎn)發(fā)時(shí)間，降低沖突，還有利于收集足夠的鄰居節(jié)點(diǎn)未覆蓋信息，調(diào)整多播數(shù)據(jù)轉(zhuǎn)發(fā)概率，提高多播數(shù)據(jù)轉(zhuǎn)發(fā)效率。[ni]節(jié)點(diǎn)的未覆蓋鄰居節(jié)點(diǎn)絕對(duì)數(shù)量，以及它和r節(jié)點(diǎn)之間的公共鄰居比率都對(duì)多播數(shù)據(jù)的轉(zhuǎn)發(fā)時(shí)延產(chǎn)生了不同的影響。以下用[Rc（nri）]標(biāo)記r節(jié)點(diǎn)和[ni]節(jié)點(diǎn)的公共鄰居比率，[Rc（nri）]定義如下：

[Rc（nri）=N（r）?N（ni）N（r）-1] ? ?（8）

式中：[·]表示集合中節(jié)點(diǎn)的數(shù)目;[N（r）-1]表示在節(jié)點(diǎn)r的鄰居中排除了節(jié)點(diǎn)ni。

用[Td（ni）]標(biāo)記[ni]的轉(zhuǎn)發(fā)時(shí)延，其定義如下：

[Td（ni）=Δ?（1-Fu（ni）?Rc（nri））， ? ? ? ?N（r）?N（ni）≠?Td（ni）=0， ? ? ? ?N（r）?N（ni）=? 或 ?nj，nj∈U（ni）&N（nj） =ni] ? ? ? ? ?（9）

式中，[Δ]是一個(gè)較小的時(shí)延常數(shù)。

多播轉(zhuǎn)發(fā)時(shí)延的取值原則如下：

1） 如果節(jié)點(diǎn)[ni]的未覆蓋鄰居節(jié)點(diǎn)絕對(duì)數(shù)量越多，那么節(jié)點(diǎn)[ni]的多播轉(zhuǎn)發(fā)時(shí)延就應(yīng)該越小。這樣有利于更多的沒有接收到多播數(shù)據(jù)的節(jié)點(diǎn)在盡可能短的時(shí)間里獲取數(shù)據(jù)，加快多播數(shù)據(jù)在網(wǎng)絡(luò)中的傳播速度，縮短端到端平均時(shí)延。

2） 如果r與[ni]的公共鄰居所占比率越大，時(shí)延就應(yīng)該越小。因?yàn)楣?jié)點(diǎn)[ni]越早轉(zhuǎn)發(fā)，就會(huì)有越多的公共鄰居接收到重發(fā)的多播數(shù)據(jù)，并及時(shí)調(diào)整自己的未覆蓋鄰居集合，進(jìn)而減小轉(zhuǎn)發(fā)概率，降低冗余數(shù)據(jù)，提高帶寬利用率。

3） N（r）[∩]N（[ni]）=[?]，即節(jié)點(diǎn)r和[ni]沒有公共鄰居時(shí)，節(jié)點(diǎn)[ni]的轉(zhuǎn)發(fā)不會(huì)引發(fā)沖突，Td（ni）為0可以加快數(shù)據(jù)的傳播。節(jié)點(diǎn)[ni]是次葉子節(jié)點(diǎn)時(shí)，必須轉(zhuǎn)發(fā)接收到的多播數(shù)據(jù)，并將Td（ni）設(shè)為0，這可以讓公共鄰居節(jié)點(diǎn)盡快更新未覆蓋信息，同時(shí)加速數(shù)據(jù)傳播。

特別規(guī)定：如果Rd（ni）的計(jì)算值小于0，那么規(guī)定Rd（ni）的取值為0。

1.5 ?基于鄰居覆蓋信息的多播通信算法描述

算法主要包括三部分：

1） 初始化未覆蓋鄰居節(jié)點(diǎn)集合U（ni），計(jì)算時(shí)延Td （ni）;

2） 更新未覆蓋鄰居節(jié)點(diǎn)集合U（ni）;

3）在轉(zhuǎn)發(fā)時(shí)延結(jié)束時(shí)計(jì)算多播數(shù)據(jù)轉(zhuǎn)發(fā)概率

pk（ni），并決定是否轉(zhuǎn)發(fā)。

2 ?基于節(jié)點(diǎn)移動(dòng)速度差異的數(shù)據(jù)傳輸方案

基于節(jié)點(diǎn)移動(dòng)速度差異的數(shù)據(jù)傳輸方案（Velocity?based Data Dissemination Scheme，VDDS）利用一部分移動(dòng)速度快的節(jié)點(diǎn)來轉(zhuǎn)發(fā)數(shù)據(jù)，以便將數(shù)據(jù)快速傳播到網(wǎng)絡(luò)中，減少時(shí)延。節(jié)點(diǎn)移動(dòng)速度信息可以通過Hello報(bào)文增加一個(gè)字段vi來收集。

假設(shè)節(jié)點(diǎn)ni有ki個(gè)鄰居節(jié)點(diǎn)，節(jié)點(diǎn)ni的移動(dòng)速度為vi，它的鄰居節(jié)點(diǎn)的移動(dòng)速度為vj（j=1，2，…，ki）。在這（ki+1）個(gè)節(jié)點(diǎn)中，速度最大的節(jié)點(diǎn)的移動(dòng)速度記為vmax （ni）：

[vmax（ni）=max（v1，v2，…，vki）] ?（10）

這（ki+1）個(gè)節(jié)點(diǎn)的平均移動(dòng)速度記為[v（ni）]：

[v（ni）=1ki+1j=1kivj+vi] （11）

這（ki+1）個(gè)節(jié)點(diǎn)移動(dòng)速度的標(biāo)準(zhǔn)差記為[σ（ni）]：

[σ（ni）=1ki+1j=1ki（vj-v（ni））2+（vi-v（ni））2] ? （12）

在基于節(jié)點(diǎn)移動(dòng)速度的數(shù)據(jù)傳輸方案中，只有當(dāng)節(jié)點(diǎn)ni的移動(dòng)速度大于平均移動(dòng)速度與移動(dòng)速度標(biāo)準(zhǔn)差之和[（vj-v（ni））]時(shí)，才需要計(jì)算節(jié)點(diǎn)ni的轉(zhuǎn)發(fā)概率，即此時(shí)節(jié)點(diǎn)ni才有可能參與數(shù)據(jù)轉(zhuǎn)發(fā)。

節(jié)點(diǎn)ni數(shù)據(jù)轉(zhuǎn)發(fā)概率pv（ni）為：

[pvni= ?0， ? ? ? vi≤vni+σnivi-vni+σnivmaxni-vni+σni，vi≤vni+σni] （13）

3 ?基于鄰居覆蓋信息和節(jié)點(diǎn)移動(dòng)速度的多播方案

將VDDS方案擴(kuò)展應(yīng)用于方案NCM，形成基于鄰居覆蓋信息和節(jié)點(diǎn)移動(dòng)速度的多播方案NCVM。NCVM是在NCM的基礎(chǔ)上額外選擇多播組中部分快速移動(dòng)的節(jié)點(diǎn)來加速數(shù)據(jù)的傳輸。在NCVM算法中，節(jié)點(diǎn)轉(zhuǎn)發(fā)多播數(shù)據(jù)的概率由節(jié)點(diǎn)的移動(dòng)速度和鄰居覆蓋信息共同決定。

NCVM算法主要包括三部分：

1） 初始化未覆蓋鄰居節(jié)點(diǎn)集合U（ni），計(jì)算基于節(jié)點(diǎn)速度的轉(zhuǎn)發(fā)概率pv（ni）。如果轉(zhuǎn)發(fā)概率落入?yún)^(qū)間（1-pv（ni））而未能轉(zhuǎn)發(fā)該多播數(shù)據(jù)，則計(jì)算時(shí)延Td（ni）。

2） 時(shí)延Td （ni）未結(jié)束之前更新未覆蓋鄰居節(jié)點(diǎn)集合U（ni）。如未覆蓋鄰居節(jié)點(diǎn)集合U（ni）更新后為空，結(jié)束計(jì)時(shí)，退出算法;否則繼續(xù)更新U（ni），直到計(jì)時(shí)結(jié)束。

3） 計(jì)算基于鄰居信息的多播數(shù)據(jù)轉(zhuǎn)發(fā)概率pk（ni），并以概率pk（ni）轉(zhuǎn)發(fā)多播數(shù)據(jù)。

NCVM算法中的函數(shù)與參數(shù)定義如下：

m：節(jié)點(diǎn)ni接收到的多播數(shù)據(jù)。

Timer（ni，m，Td（ni））：計(jì)時(shí)器，節(jié)點(diǎn)ni第一次接收到多播數(shù)據(jù)m時(shí)設(shè)定，值為Td（ni）。

random（0，1）：值域介于（0，1）區(qū)間的隨機(jī)函數(shù)。

基于鄰居信息和節(jié)點(diǎn)移動(dòng)速度的多播通信算法如下：

/*初始化未覆蓋鄰居節(jié)點(diǎn)集合[U（ni）]*/

1.While ni receives a fresh multicast message m from r do

2.[U（ni）=N（ni）-[N（ni）?N（r）]-{r}]

3.if [U（ni） =] [?] then

4. [p（ni）] = 0 and return

5.end if

/*計(jì)算基于節(jié)點(diǎn)速度的轉(zhuǎn)發(fā)概率[pvni]*/

6.if [vi>v（ni）+σ（ni）] then

7.[pvni=vi-（v（ni）+σ（ni））vmax（ni）-（v（ni）+σ（ni））]

8.if random（0，1）≤pv（ni） then

9.forwarding （m） and return

10.end if

11.end if

/*計(jì)算轉(zhuǎn)發(fā)時(shí)延Td（ni）*/

12.if [N（r）?N（ni）=?或?nj， N（nj） =ni] then

13.Td（ni）= 0

14.else

15.[Td（ni）=Δ·Rd（ni）]

16.Set a Timer（ni，m，Td（ni））

17.end if

18.end while

/*更新未覆蓋鄰居節(jié)點(diǎn)集合U（ni）*/

19. while ni receives a duplicate m from nj before Timer（ni，m，Td（ni）） expires do

20.[Uni=Uni-[Uni?Nni]]

21.if [U（ni）=?] then

22.p（ni） = 0 and return

23.end if

24.end while

/*計(jì)算基于鄰居信息的多播數(shù)據(jù)轉(zhuǎn)發(fā)概率pk（ni），并以概率pk（ni）進(jìn)行轉(zhuǎn)發(fā)*/

25.While Timer（ni，m，Td（ni）） expires do

26.if [ ?nj， N（nj） =ni] then

27.pk（ni）=1

28.else

29.[pk（ni）=[β·Ru（ni）+（1-β）·Fu（ni）]/d（ni）]

30.end if

31.if random（0，1） ≤[pk（ni）] then

32.forwarding （m） and return

33.end if

34.end while

4 ?仿真實(shí)驗(yàn)與結(jié)果分析

采用NS?2.35[13]對(duì)本文提出的NCM及NCVM方案、Ncast[2]、ODMRP[6]方案及泛洪方案[14]進(jìn)行仿真。實(shí)驗(yàn)分別模擬了不同節(jié)點(diǎn)移動(dòng)速度、不同節(jié)點(diǎn)數(shù)的網(wǎng)絡(luò)環(huán)境，以分析它們對(duì)多播方案的開銷、端到端時(shí)延、分組投遞率的影響，方案的性能參數(shù)定義如下：

1） 分組傳輸開銷（Packet Transmission Overhead）。所有轉(zhuǎn)發(fā)的多播分組與目的節(jié)點(diǎn)接收到的有效分組之比。

2） 控制開銷（Control Overhead）。每傳送一個(gè)字節(jié)的多播數(shù)據(jù)所產(chǎn)生的控制分組字節(jié)數(shù)。

3） 端到端平均時(shí)延（Average End?to?End Delay）。多播數(shù)據(jù)從源節(jié)點(diǎn)發(fā)出到被目的節(jié)點(diǎn)接收的平均時(shí)間間隔。

4） 分組投遞率（Packet Delivery Ratio）。收到多播數(shù)據(jù)的成員節(jié)點(diǎn)數(shù)與所有成員節(jié)點(diǎn)數(shù)之比。

4.1 ?實(shí)驗(yàn)環(huán)境設(shè)置

模擬中采用隨機(jī)路點(diǎn)移動(dòng)模型（Random Waypoint Model）來模擬移動(dòng)自組網(wǎng)中節(jié)點(diǎn)的移動(dòng)，節(jié)點(diǎn)被固定在1 000 m×1 000 m（Topology Size）的正方形區(qū)域內(nèi)移動(dòng)。置信度設(shè)定為95%，詳細(xì)的模擬參數(shù)如表1所示。

表1 ?基于鄰居覆蓋信息的多播方案模擬參數(shù)

[模擬參數(shù) 參數(shù)值 節(jié)點(diǎn)數(shù) 50， 100， 150， 200， 250， 300 節(jié)點(diǎn)信號(hào)傳輸半徑 /m 250 鏈路帶寬 /（Mb/s） 2 流量類型 CBR 分組大小 /B 512 分組發(fā)送率 /（packets/sec） 4 駐留時(shí)間 /s 0 節(jié)點(diǎn)最大移動(dòng)速度 /（m/s） 0， 5， 10， 15， 20， 25 MAC層協(xié)議 IEEE 802.11 DCF CSMA/CA Hello 報(bào)文發(fā)送周期 /s 4 轉(zhuǎn)發(fā)時(shí)延常數(shù)（Δ） /s 0.01 β（NCM，NCVM） 0.8 join query報(bào)文周期（ODMRP） /s 3 ADV報(bào)文周期（NCast） /s 3 ]

4.2 ?節(jié)點(diǎn)移動(dòng)速度對(duì)多播方案性能的影響

實(shí)驗(yàn)中節(jié)點(diǎn)的最大移動(dòng)速度取值范圍為0～25 m/s，網(wǎng)絡(luò)中節(jié)點(diǎn)的數(shù)目為200，CBR連接數(shù)為20。

圖2展示了節(jié)點(diǎn)移動(dòng)速度對(duì)多播數(shù)據(jù)傳輸開銷的影響。NCVM中有部分移動(dòng)速度較快的節(jié)點(diǎn)參與了數(shù)據(jù)的轉(zhuǎn)發(fā)，其分組傳輸開銷略大于NCM。NCM和NCVM通過感知鄰居節(jié)點(diǎn)的未覆蓋信息和節(jié)點(diǎn)密度來動(dòng)態(tài)調(diào)整多播數(shù)據(jù)轉(zhuǎn)發(fā)概率，其轉(zhuǎn)發(fā)概率的自適應(yīng)性有效減少了冗余分組，降低了沖突。并且引入的隨機(jī)時(shí)延有效地錯(cuò)開相鄰節(jié)點(diǎn)的數(shù)據(jù)轉(zhuǎn)發(fā)時(shí)間，減少對(duì)信道的競(jìng)爭(zhēng)，降低了分組傳輸開銷。相比其他方案，節(jié)點(diǎn)移動(dòng)速度對(duì)NCM和NCVM的分組傳輸開銷影響較小。

圖2 ?節(jié)點(diǎn)移動(dòng)速度對(duì)分組傳輸開銷的影響

flooding是五個(gè)方案中分組傳輸開銷最多的一個(gè)。ODMRP方案的冗余分組和節(jié)點(diǎn)移動(dòng)造成的重傳增加了分組傳輸開銷。Ncast協(xié)議的分組傳輸開銷最小，體現(xiàn)了樹結(jié)構(gòu)的高效性，但這是以分組投遞率下降為代價(jià)的，如圖3所示。

圖3 ?節(jié)點(diǎn)移動(dòng)速度對(duì)分組投遞率的影響

圖3呈現(xiàn)了節(jié)點(diǎn)移動(dòng)速度對(duì)分組投遞率的影響。flooding協(xié)議獲得了最高的分組投遞率?；诰W(wǎng)格的ODMRP分組投遞率優(yōu)于基于樹結(jié)構(gòu)的NCast。當(dāng)節(jié)點(diǎn)移動(dòng)速度大于5 m/s時(shí)，相比NCast方案，NCM和NCVM方案將分組投遞率提高了4.99%～27.4%和5.1%～28.8%。

圖4呈現(xiàn)了節(jié)點(diǎn)移動(dòng)速度對(duì)控制開銷的影響。flooding方案不產(chǎn)生控制開銷。ODMRP方案周期性的泛洪和轉(zhuǎn)發(fā)組的維護(hù)都產(chǎn)生了大量的控制開銷，并帶來時(shí)延，如圖4、圖5所示。節(jié)點(diǎn)移動(dòng)引起的樹結(jié)構(gòu)的頻繁重構(gòu)造成NCast方案控制開銷急劇上升，時(shí)延也因此而增加。NCM和NCVM利用捎帶技術(shù)和少量Hello報(bào)文維持松散的成員關(guān)系，受節(jié)點(diǎn)移動(dòng)影響小，控制開銷少。相對(duì)于NCast方案，它們將控制開銷降低了4.3%～23.2%。

圖4 ?節(jié)點(diǎn)移動(dòng)速度對(duì)控制開銷的影響

圖5 ?節(jié)點(diǎn)移動(dòng)速度對(duì)端到端平均時(shí)延的影響

圖5呈現(xiàn)了節(jié)點(diǎn)移動(dòng)速度對(duì)端到端平均時(shí)延的影響。flooding協(xié)議、NCM和NCVM方案在節(jié)點(diǎn)移動(dòng)速度加快時(shí)時(shí)延反而減小，因?yàn)閿y帶多播數(shù)據(jù)的快速移動(dòng)節(jié)點(diǎn)加快了分組的傳播。NCM方案中引入了隨機(jī)轉(zhuǎn)發(fā)時(shí)延，增加了端到端平均時(shí)延，但轉(zhuǎn)發(fā)時(shí)延會(huì)降低信道的競(jìng)爭(zhēng)和傳輸沖突，提高了分組的傳播速度，反過來一定程度上又降低了端到端平均時(shí)延。相比NCast方案，NCM和NCVM方案將端到端平均時(shí)延分別降低了7.23%～36.9%和8.09%～45.9%。

4.3 ?節(jié)點(diǎn)密度對(duì)多播方案性能的影響

多播組成員節(jié)點(diǎn)數(shù)目取值分別為50，100，150，200，250，節(jié)點(diǎn)的最大移動(dòng)速度為15 m/s，CBR連接數(shù)為20。圖6呈現(xiàn)了成員節(jié)點(diǎn)數(shù)對(duì)分組傳輸開銷的影響。flooding轉(zhuǎn)發(fā)的冗余分組最多，產(chǎn)生沖突多，分組傳輸開銷增長最快。同時(shí)，沖突的增加還導(dǎo)致了時(shí)延的增長，分組投遞率的下降，如圖7、圖8所示。但與其他4個(gè)協(xié)議相比，flooding的分組投遞率最高。

圖6 ?成員節(jié)點(diǎn)數(shù)對(duì)分組傳輸開銷的影響

節(jié)點(diǎn)的移動(dòng)和數(shù)目的增加使得ODMRP的網(wǎng)格維護(hù)變得更加復(fù)雜，沖突增多。當(dāng)節(jié)點(diǎn)數(shù)目達(dá)到150時(shí)，分組傳輸開銷增加明顯，控制開銷增速更快，時(shí)延隨之增加，如圖6、圖7、圖9所示。節(jié)點(diǎn)數(shù)目密度增加使得ODMRP的分發(fā)組中的冗余鏈路增多，分組投遞率受節(jié)點(diǎn)移動(dòng)的影響反而被弱化了，一直保持在95%以上見圖8。

圖7 ?成員節(jié)點(diǎn)數(shù)對(duì)端到端平均時(shí)延的影響

圖8 ?成員節(jié)點(diǎn)數(shù)對(duì)分組投遞率的影響

基于樹結(jié)構(gòu)的NCast保持了較低的分組傳輸開銷。節(jié)點(diǎn)密度較大時(shí)因沖突的增加，NCast的分組傳輸開銷和端到端平均時(shí)延略有增加，如圖6、圖7所示。節(jié)點(diǎn)增加時(shí)，分發(fā)樹的規(guī)模也變大，維護(hù)開銷增多，同時(shí)受節(jié)點(diǎn)移動(dòng)的影響，控制開銷有所增加，如圖9所示。但成員節(jié)點(diǎn)數(shù)的增加提高了網(wǎng)絡(luò)的連通性，分發(fā)樹重構(gòu)變得容易，因而NCast的分組投遞率有所提高，但仍然遠(yuǎn)低于其他4個(gè)多播方案，如圖8所示。

圖9 ?成員節(jié)點(diǎn)數(shù)對(duì)控制開銷的影響

NCM和NCVM方案在計(jì)算轉(zhuǎn)發(fā)時(shí)延和轉(zhuǎn)發(fā)概率時(shí)都引入了節(jié)點(diǎn)密度參數(shù)，有效降低了節(jié)點(diǎn)密度對(duì)方案性能的負(fù)面影響。與NCM相比，NCVM方案的最大的優(yōu)勢(shì)在于顯著降低了分組時(shí)延，并提高了分組投遞率，如圖7、圖8所示。與NCast方案相比，NCM和NCVM方案分別將控制開銷降低了2.42%～27.5%，2.27%～27.4%;分別將端到端平均時(shí)延降低了11.4%～24.3%，16.1%～32.3%;分別將分組投遞率提高了15.6%～27.1%，16.3%～27.3%。

5 ?結(jié) ?語

本文針對(duì)節(jié)點(diǎn)移動(dòng)速度與節(jié)點(diǎn)分布時(shí)刻變化的無線自組網(wǎng)提出NCM和NCVM多播方案。方案通過Hello報(bào)文收集鄰居密度和覆蓋信息，實(shí)時(shí)計(jì)算每個(gè)節(jié)點(diǎn)的轉(zhuǎn)發(fā)時(shí)延和概率。一跳鄰居信息的收集保證了控制開銷處于較低水平，靈活的轉(zhuǎn)發(fā)時(shí)延和概率計(jì)算保證了復(fù)雜移動(dòng)環(huán)境下的端到端平均時(shí)延以及高分組傳輸率。此外，多播轉(zhuǎn)發(fā)時(shí)延和概率的定義方法有利于平衡業(yè)務(wù)負(fù)載，提高方案的可擴(kuò)展性。為了進(jìn)一步降低時(shí)延，在NKVB方案中少數(shù)高速節(jié)點(diǎn)被用于轉(zhuǎn)發(fā)多播消息，加快傳播速度，使得NKVB方案更適合于移動(dòng)環(huán)境。仿真結(jié)果表明，NCM和NCVM方案在可靠性和開銷上均優(yōu)于現(xiàn)有的多播方案，尤其是在時(shí)延方面表現(xiàn)突出，具備優(yōu)秀的動(dòng)態(tài)網(wǎng)絡(luò)環(huán)境適應(yīng)能力。

參考文獻(xiàn)

[1] KUMAR W G， NEERAJ M. A survey of multicast routing protocols in MANET [J]. IITM journal of management and IT， 2017， 8（1）： 42?50.

[2] NARGESI A A， BAG?MOHAMMADI M. Efficient multicast tree construction in wireless mesh networks [J]. Journal of communications and networks， 2014， 16（6）： 613?619.

[3] GONG H， FU L， FU X， et al. Distributed multicast tree construction in wireless sensor networks [J]. IEEE transactions on information theory， 2017， 63（1）： 280?296.

[4] LU T， ZHU J， CHANG S， et al. Maximizing multicast lifetime in unreliable wireless ad hoc network [J]. Wireless networks， 2018， 24（4）： 1175?1185.

[5] BOUSBAA F Z， LAGRAA N， KERRACHE C A， et al. A distributed time?limited multicast algorithm for VANETs using incremental power strategy [J]. Computer networks， 2018， 145： 141?155.

[6] LEE S J， SU W， GERLA M. On?demand multicast routing protocol in multi?hop wireless mobile networks [J]. Mobile networks and applications， 2002， 7（6）： 441?453.

[7] YAN Y， TIAN K， HUANG K， et al. D?ODMRP： a destination?driven on?demand multicast routing protocol for mobile ad hoc networks [J]. IET communications， 2012， 6（9）： 1025?1031.

[8] ZHANG C， LIU Y， REN X， et al. LSODMRP： improved?ODMRP multicast routing protocol based on local broadcast and stable links for MANET [C]// Proceedings of International Conference in Communications， Signal Processing and Systems. Singapore： Springer， 2017： 574?581.

[9] LEE S J， SU W， HSU J， et al. A performance comparison study of ad hoc wireless multicast protocols [C]// Proceedings of 19th Annual Joint Conference of the IEEE Computer and Communications Societies. Tel Aviv： IEEE， 2000： 565?574.

[10] JIA W， LU D， WANG G， et al. Local retransmission?based gossip protocol in mobile ad hoc networks [C]// Proceedings of IEEE Wireless Communications & Networking Conference. Kowloon： IEEE， 2007： 4244?4249.

[11] LU D， DONG S， JIAO D. NKBM： a neighbor knowledge?based multicast scheme for dense wireless mesh networks [C]// Proceedings of 34th Chinese Control Conference. Hangzhou： IEEE， 2015： 1451?1456.

[12] XUE F， KUMAR P R. The number of neighbors needed for connectivity of wireless networks [J]. Wireless networks， 2004， 10（2）： 169?181.

[13] Anon. The network simulator： building?Ns?2 [EB/OL]. [2017?10?18]. https：//www.isi.edu/nsnam/ns/.

[14] JETCHEVA J G， HU Y C， MALTZ D A， et al. A simple protocol for multicast and broadcast in mobile ad hoc networks [EB/OL]. [2000?07?20]. https：//art.tools.ietf.org/html/draft?ietf?manet?simple?mbcast?01.