楊茂保 徐利亞 葛明珠 舒長(zhǎng)興

（九江學(xué)院，九江332005）

主題詞：車(chē)載網(wǎng) 緊急信息 廣播路由

1 前言

車(chē)載自組織網(wǎng)絡(luò)（Vehicular Ad hoc Network，VANET）是一種將傳感器技術(shù)、短距離移動(dòng)通信及信息處理技術(shù)相結(jié)合的移動(dòng)自組網(wǎng)（Mobile Ad hoc Network，MANET），是智能交通系統(tǒng)的基礎(chǔ)信息承載平臺(tái)。VANET中的節(jié)點(diǎn)主要由車(chē)輛組成，車(chē)輛可利用車(chē)載傳感器實(shí)時(shí)采集交通信息，通過(guò)與其他車(chē)輛的交流來(lái)廣播安全、道路狀況等信息，在改善交通環(huán)境、減少交通事故等方面具有積極的作用[1]。此外，在VANET中，車(chē)輛還可以與路側(cè)單元（Road Side Units，RSU）通信，通過(guò)RSU接入主干網(wǎng)，為車(chē)內(nèi)成員提供更豐富的服務(wù)[2-5]。

車(chē)載網(wǎng)中的廣播路由算法主要有基于地理位置的路由[6-9]、基于內(nèi)容的路由[10-14]?；诘乩砦恢玫膹V播路由算法的優(yōu)點(diǎn)是實(shí)現(xiàn)較簡(jiǎn)單、執(zhí)行效率高，通?；诘乩砦恢脛澐趾蜻x節(jié)點(diǎn)，選擇距離廣播節(jié)點(diǎn)更遠(yuǎn)的節(jié)點(diǎn)作為下一跳中繼節(jié)點(diǎn)來(lái)轉(zhuǎn)發(fā)數(shù)據(jù)包，但該類算法沒(méi)有很好地顧及到VANET中車(chē)輛節(jié)點(diǎn)移動(dòng)速度快、網(wǎng)絡(luò)拓?fù)渥兓斓奶攸c(diǎn)，當(dāng)數(shù)據(jù)包傳輸?shù)杰?chē)輛節(jié)點(diǎn)稀少的路段時(shí)，會(huì)產(chǎn)生極大的延時(shí)?；趦?nèi)容的廣播路由算法中，數(shù)據(jù)包含有本地拓?fù)湫畔ⅲ芨咝实剡x擇中繼節(jié)點(diǎn)來(lái)傳輸數(shù)據(jù)包，但由于拓?fù)渥兓?，?huì)產(chǎn)生冗余，當(dāng)節(jié)點(diǎn)緩存已滿時(shí)會(huì)造成數(shù)據(jù)包的丟失。

因此，信息在車(chē)載網(wǎng)絡(luò)中的傳輸面臨諸多挑戰(zhàn)：節(jié)點(diǎn)密度大、車(chē)速快使得網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)變化極快，節(jié)點(diǎn)間形成的鏈路持續(xù)時(shí)間較短；節(jié)點(diǎn)的移動(dòng)受道路的強(qiáng)制約束，使得網(wǎng)絡(luò)中節(jié)點(diǎn)分布不均勻，造成VANET中嚴(yán)重的網(wǎng)絡(luò)分割現(xiàn)象；在道路區(qū)域，特別是熱點(diǎn)區(qū)域（如交叉路口周?chē)?，?jié)點(diǎn)的密度巨大，如不加限制地使所有節(jié)點(diǎn)自由廣播信息，會(huì)帶來(lái)激烈的信道資源競(jìng)爭(zhēng)，使得該區(qū)域的無(wú)線傳輸癱瘓。這些因素導(dǎo)致信息在VANET中的傳輸不穩(wěn)定，本文提出一種低延時(shí)的廣播路由，通過(guò)建立連通支配集，概率廣播數(shù)據(jù)包來(lái)減少傳輸沖突。

2 單位圓盤(pán)圖

本文討論的VANET場(chǎng)景采用全向傳輸方式。根據(jù)全向傳輸方式中無(wú)線覆蓋區(qū)域呈圓盤(pán)狀的特點(diǎn)，該區(qū)域可用單位圓盤(pán)圖（Unit-Disk Graph，UDG）[15]表示，即G=(V,E)，其中，V為節(jié)點(diǎn)集，E為邊集，即兩點(diǎn)之間可形成鏈路。

以發(fā)送節(jié)點(diǎn)的位置為圓心，以無(wú)線通信最大傳輸范圍為半徑，且假設(shè)節(jié)點(diǎn)的最大無(wú)線傳輸范圍相同，如果節(jié)點(diǎn)在另一個(gè)節(jié)點(diǎn)的通信范圍內(nèi)，則這兩個(gè)節(jié)點(diǎn)可以通信，即它們之間存在一條鏈路。

在UDG模型中，每個(gè)節(jié)點(diǎn)都有唯一的ID以標(biāo)識(shí)身份。|V|表示網(wǎng)絡(luò)中節(jié)點(diǎn)的數(shù)量，|S|表示任意節(jié)點(diǎn)集合S?V(G)中節(jié)點(diǎn)的數(shù)量，|E|表示邊的數(shù)量。以(vi,vj)∈E(G)表示節(jié)點(diǎn)vi和vj有直接連接的邊，即vi與vj相鄰，節(jié)點(diǎn)vi和節(jié)點(diǎn)vj互為鄰居節(jié)點(diǎn)。

連通支配集（Connected Dominating Set，CDS）是圓盤(pán)圖G中的節(jié)點(diǎn)集合D?V(G)，對(duì)任一節(jié)點(diǎn)v，v∈U或者v是D中節(jié)點(diǎn)的鄰居節(jié)點(diǎn)。

若v是圖G中的一節(jié)點(diǎn)，集合Neighbor(v)表示v的鄰居集。

d(u1,u2)為頂點(diǎn)u1、u2之間的距離，R為節(jié)點(diǎn)最大傳輸距離，如果d(u1,u2)＜R，則頂點(diǎn)u1和u2有一條連通的邊。

U是節(jié)點(diǎn)內(nèi)維護(hù)的集合，存放當(dāng)前節(jié)點(diǎn)為中心長(zhǎng)度為d的路段內(nèi)的所有節(jié)點(diǎn)。

3 路由選擇

本文提出的廣播路由方法為：對(duì)VANET熱點(diǎn)區(qū)域中的車(chē)輛節(jié)點(diǎn)構(gòu)造CDS；對(duì)每個(gè)要傳輸?shù)臄?shù)據(jù)包，選擇CDS中的節(jié)點(diǎn)作為廣播路由的中繼車(chē)輛節(jié)點(diǎn)，并按一定的概率廣播。

3.1 連通支配集的構(gòu)造算法

車(chē)輛節(jié)點(diǎn)的傳輸模型是UDG，然而在圖中，計(jì)算最小連通支配集（Minimum Connected Dominating Set，MCDS）是不確定多項(xiàng)式時(shí)間問(wèn)題（Non-deterministic Polynomial-time hard，NP-hard）[16]，即在多項(xiàng)式時(shí)間內(nèi)不收斂，得不出解。本文研究該問(wèn)題的近似解，即構(gòu)建一個(gè)近似最小的CDS算法。

3.1.1 算法描述

構(gòu)建以當(dāng)前節(jié)點(diǎn)S為中心的通信范圍內(nèi)初始連通圖G(V,E)，用最小生成樹(shù)思想[17]構(gòu)造1個(gè)初始CDS。要使CDS內(nèi)的節(jié)點(diǎn)數(shù)更少，則要保證選入CDS內(nèi)的節(jié)點(diǎn)具有更多的鄰居節(jié)點(diǎn)，構(gòu)建M-CDS。在圖G(V,E)中，當(dāng)前節(jié)點(diǎn)的鄰居節(jié)點(diǎn)數(shù)即為該節(jié)點(diǎn)的度，所以在選擇CDS內(nèi)的節(jié)點(diǎn)時(shí)，將節(jié)點(diǎn)的度作為權(quán)衡參數(shù)，節(jié)點(diǎn)的度越大，其權(quán)值越高。

3.1.2 算法實(shí)現(xiàn)

構(gòu)建VANET中以源（source）節(jié)點(diǎn)為中心，長(zhǎng)度為d的區(qū)域內(nèi)的CDS，并將該CDS廣播到區(qū)域內(nèi)的所有節(jié)點(diǎn)。構(gòu)建的初始圖G(V,E)算法和M-CDS算法流程分別如圖1、圖2所示，其中，u0為source頂點(diǎn)，CDSinitial為初始連通支配集。

圖1 初始圖G(V,E)算法流程

圖2 M-CDS算法流程

3.1.3 算法分析

初始圖G（V，E）算法是依據(jù)數(shù)據(jù)結(jié)構(gòu)中經(jīng)典的構(gòu)造圖方法建立的，時(shí)間復(fù)雜度為O(n3)。M-CDS算法的時(shí)間復(fù)雜度分析過(guò)程為：

a.賦權(quán)值給圖中的各邊，其時(shí)間復(fù)雜度為O(n)。

b.Prim算法生成最小生成樹(shù)的時(shí)間復(fù)雜度為O(n2)。

c.選擇非葉子節(jié)點(diǎn)。對(duì)于構(gòu)建好的最小生成樹(shù)中的節(jié)點(diǎn)，易知只需依次判斷節(jié)點(diǎn)的度是否為1即可，故該部分的時(shí)間復(fù)雜度為O(n)。

d.去除冗余的節(jié)點(diǎn)。需要將初始支配集中的節(jié)點(diǎn)兩兩進(jìn)行鄰居節(jié)點(diǎn)對(duì)比。對(duì)于n個(gè)節(jié)點(diǎn)，兩兩遍歷需要查詢的次數(shù)是n(n-1)/2。假設(shè)兩節(jié)點(diǎn)擁有的鄰居節(jié)點(diǎn)數(shù)分別為m1和m2，鄰居節(jié)點(diǎn)集中的節(jié)點(diǎn)以ID按序排列，則判斷兩節(jié)點(diǎn)的鄰居集是否存在包含關(guān)系需要的查詢次數(shù)為max{m1,m2}。在一個(gè)網(wǎng)絡(luò)中，當(dāng)每個(gè)節(jié)點(diǎn)擁有的鄰居節(jié)點(diǎn)數(shù)超過(guò)5.177 4logn[18]時(shí)，該網(wǎng)絡(luò)是全連通的，因此，m1、m2均小于5.177 4logn，則該步的時(shí)間復(fù)雜度為O(n2logn)。

由于上述步驟是順序執(zhí)行的，所以構(gòu)建CDS的時(shí)間復(fù)雜度是O(n2logn)。

3.1.4 結(jié)果分析

選擇經(jīng)典的貪心算法（Greedy Algorithm）和Rule-K算法，在靜態(tài)拓?fù)鋱?chǎng)景下與本文提出的M-CDS算法進(jìn)行比較，然后按照VANET場(chǎng)景設(shè)置節(jié)點(diǎn)傳輸半徑R和隨機(jī)圖中的節(jié)點(diǎn)數(shù)n，得到CDS內(nèi)的節(jié)點(diǎn)數(shù)量與傳輸半徑R和圖中節(jié)點(diǎn)數(shù)n的關(guān)系，如圖3所示。

圖3 CDS內(nèi)的節(jié)點(diǎn)數(shù)量隨圖中節(jié)點(diǎn)數(shù)量的變化

由圖3a可知，當(dāng)R=30 m時(shí)，貪心算法生成CDS內(nèi)的節(jié)點(diǎn)數(shù)量較Rule-K算法和M-CDS算法多。當(dāng)節(jié)點(diǎn)數(shù)較少時(shí)，M-CDS算法的表現(xiàn)與Rule-K算法較為接近，但隨著節(jié)點(diǎn)數(shù)的增多，Rule-K算法的性能略勝一籌。這是因?yàn)殡S著節(jié)點(diǎn)的增多，CDS內(nèi)的節(jié)點(diǎn)數(shù)量隨之增加，導(dǎo)致邊界網(wǎng)關(guān)增多。Rule-K算法去除冗余節(jié)點(diǎn)的規(guī)則比M-CDS更為精確，能最大限度地得出MCDS，但是其相應(yīng)的開(kāi)銷稍大些，相反，M-CDS算法實(shí)現(xiàn)簡(jiǎn)單，開(kāi)銷相對(duì)較小。

由圖3b可知，當(dāng)R=100 m時(shí)，貪心算法生成CDS內(nèi)的節(jié)點(diǎn)數(shù)量依然較其他2個(gè)算法大，而Rule-K算法與M-CDS算法生成的CDS較為接近。這是由于節(jié)點(diǎn)傳輸半徑增大使得節(jié)點(diǎn)鄰居數(shù)大量增加，M-CDS算法生成的CDS中每個(gè)節(jié)點(diǎn)擁有更多葉子節(jié)點(diǎn)，生成初始的CDS時(shí)會(huì)刪除所有的葉子節(jié)點(diǎn)，即刪除的冗余節(jié)點(diǎn)也更多。

在本文場(chǎng)景中，選擇長(zhǎng)為10 km、寬為25 m的矩形區(qū)域，隨機(jī)投放一定數(shù)量的車(chē)輛節(jié)點(diǎn)，每個(gè)車(chē)輛節(jié)點(diǎn)的連通半徑為R=200 m，距離小于R的車(chē)輛節(jié)點(diǎn)間能夠通信，反之不能通信。每次隨機(jī)產(chǎn)生的圖如果是連通的，則繼續(xù)試驗(yàn)，否則重新產(chǎn)生隨機(jī)圖。

設(shè)R=200 m，車(chē)輛節(jié)點(diǎn)數(shù)量n的變化范圍是10～100，對(duì)每個(gè)n，生成100次網(wǎng)絡(luò)拓?fù)鋱D，求解圖中CDS內(nèi)節(jié)點(diǎn)的數(shù)量，取平均值，結(jié)果如圖4所示。

圖4 R=200 m時(shí)CDS的節(jié)點(diǎn)數(shù)量隨圖中的節(jié)點(diǎn)數(shù)量的變化

由圖4可知，CDS中包含的節(jié)點(diǎn)數(shù)量隨圖中節(jié)點(diǎn)數(shù)量的增加而增加，當(dāng)節(jié)點(diǎn)數(shù)達(dá)到100時(shí)，產(chǎn)生的隨機(jī)圖已經(jīng)非常稠密，但是由M-CDS算法產(chǎn)生的CDS所包含的節(jié)點(diǎn)數(shù)卻較少。

設(shè)n=20，R的變化范圍為100～200 m，進(jìn)行100次試驗(yàn)，取平均值，結(jié)果如圖5所示。

圖5 n=20時(shí)CDS的節(jié)點(diǎn)數(shù)量隨節(jié)點(diǎn)傳輸半徑的變化

由圖5可知，當(dāng)節(jié)點(diǎn)傳輸半徑增加時(shí)，CDS的數(shù)量減少，但CDS中包含的節(jié)點(diǎn)數(shù)量增加。當(dāng)R=200 m時(shí)，CDS的數(shù)量幾乎為1，因?yàn)槔碚撋洗藭r(shí)幾乎能覆蓋到區(qū)域內(nèi)的所有節(jié)點(diǎn)。

3.2 概率廣播

構(gòu)建M-CDS后，本文以CDS中的節(jié)點(diǎn)作為廣播節(jié)點(diǎn)來(lái)廣播數(shù)據(jù)包。為了進(jìn)一步減少節(jié)點(diǎn)的廣播數(shù)據(jù)包數(shù)量、減少傳輸沖突、提高信道利用率，本文針對(duì)CDS中的節(jié)點(diǎn)，提出一種動(dòng)態(tài)的按概率廣播的策略廣播數(shù)據(jù)包，根據(jù)節(jié)點(diǎn)的密度和鄰居覆蓋集計(jì)算節(jié)點(diǎn)的廣播概率。

3.2.1 節(jié)點(diǎn)平均密度的計(jì)算

本文根據(jù)局部鄰居節(jié)點(diǎn)信息來(lái)計(jì)算網(wǎng)絡(luò)中局部節(jié)點(diǎn)的密度。如果某節(jié)點(diǎn)的鄰居節(jié)點(diǎn)數(shù)比網(wǎng)絡(luò)中節(jié)點(diǎn)的平均鄰居節(jié)點(diǎn)數(shù)多，則認(rèn)為該節(jié)點(diǎn)所處的區(qū)域是節(jié)點(diǎn)密度大的區(qū)域，反之是節(jié)點(diǎn)密度稀疏的區(qū)域。

網(wǎng)絡(luò)中節(jié)點(diǎn)的平均鄰居數(shù)量為：

式中，N為網(wǎng)絡(luò)中節(jié)點(diǎn)的總數(shù)量；Ui為節(jié)點(diǎn)i的鄰居數(shù)量。

3.2.2 節(jié)點(diǎn)的鄰居覆蓋集設(shè)定

本文的目標(biāo)是當(dāng)傳輸路由請(qǐng)求（Route Request，RREQ）包時(shí)，減少冗余包的傳輸，從而不影響網(wǎng)絡(luò)吞吐量。根據(jù)節(jié)點(diǎn)所在區(qū)域的節(jié)點(diǎn)密度和廣播包已覆蓋的鄰居節(jié)點(diǎn)集來(lái)動(dòng)態(tài)設(shè)定當(dāng)前節(jié)點(diǎn)廣播該數(shù)據(jù)包的概率。節(jié)點(diǎn)根據(jù)接收到的RREQ包中的節(jié)點(diǎn)信息更新自己的鄰居節(jié)點(diǎn)表，并確定該RREQ包已覆蓋的鄰居節(jié)點(diǎn)集。如果當(dāng)前節(jié)點(diǎn)的一跳鄰居節(jié)點(diǎn)已經(jīng)有相當(dāng)部分被該RREQ包覆蓋，則當(dāng)前節(jié)點(diǎn)廣播該RREQ包的概率較低。

節(jié)點(diǎn)的數(shù)據(jù)包覆蓋鄰居集指已經(jīng)接收到同一個(gè)數(shù)據(jù)包的該節(jié)點(diǎn)的一跳鄰居節(jié)點(diǎn)集。如圖6所示，節(jié)點(diǎn)S將RREQ包廣播到它的鄰居節(jié)點(diǎn)A、B、C、D、E，由于節(jié)點(diǎn)C和節(jié)點(diǎn)E是D的鄰居節(jié)點(diǎn)且已經(jīng)收到了同樣的RREQ包，所以對(duì)于該RREQ包，D的鄰居覆蓋集就是節(jié)點(diǎn)C和節(jié)點(diǎn)E。

圖6 節(jié)點(diǎn)的數(shù)據(jù)包覆蓋鄰居集示意

3.2.3 節(jié)點(diǎn)廣播數(shù)據(jù)包的概率

M-CDS構(gòu)建完畢后，根據(jù)前文的結(jié)果計(jì)算數(shù)據(jù)包被當(dāng)前節(jié)點(diǎn)u廣播的概率：

式中，?為當(dāng)前節(jié)點(diǎn)的鄰居覆蓋集中的節(jié)點(diǎn)數(shù)量；k為當(dāng)前節(jié)點(diǎn)的鄰居節(jié)點(diǎn)數(shù)。

4 性能評(píng)估和分析

對(duì)數(shù)據(jù)包從當(dāng)前節(jié)點(diǎn)廣播到目標(biāo)區(qū)域中所有節(jié)點(diǎn)時(shí)所產(chǎn)生的延時(shí)和數(shù)據(jù)包的遞送率進(jìn)行仿真測(cè)試，參數(shù)設(shè)置如表1所示。

首先將本文提出的低延時(shí)廣播路由（Low Latency Broadcast Routing，LLBR）與最基本的洪泛廣播進(jìn)行比較，數(shù)據(jù)包生成率為10個(gè)/s，結(jié)果如圖7所示。

表1 仿真參數(shù)

圖7 LLBR與洪泛廣播的仿真結(jié)果

由圖7可知：當(dāng)節(jié)點(diǎn)數(shù)量較少時(shí)，兩種方法的數(shù)據(jù)包遞送率都接近為1，洪泛廣播的平均端到端延時(shí)小于本文所提出的廣播方法；隨著熱點(diǎn)區(qū)域中節(jié)點(diǎn)數(shù)量增多，洪泛廣播中的數(shù)據(jù)包遞送率下降明顯，而本文提出的廣播方法遞送率仍接近1，洪泛廣播產(chǎn)生的平均端到端延時(shí)幾乎呈線性增加，而本文提出的廣播方法產(chǎn)生的延時(shí)增加不明顯。節(jié)點(diǎn)數(shù)量少時(shí)，廣播的數(shù)據(jù)包較少，不會(huì)產(chǎn)生傳輸沖突，所以遞送率高；節(jié)點(diǎn)數(shù)量增加時(shí)，洪泛廣播中每個(gè)節(jié)點(diǎn)都廣播所接收到的數(shù)據(jù)包，數(shù)據(jù)包數(shù)量呈指數(shù)增加，所產(chǎn)生的沖突急劇增多，造成數(shù)據(jù)包的丟失增多，端到端延時(shí)也急劇增加，而本文提出的廣播方法構(gòu)建區(qū)域中的CDS，通過(guò)支配集中的節(jié)點(diǎn)對(duì)數(shù)據(jù)包進(jìn)行概率廣播，極大地減少了廣播的數(shù)據(jù)包數(shù)量，遞送率和端到端延時(shí)與節(jié)點(diǎn)數(shù)較少的場(chǎng)景無(wú)明顯差異。

將本文提出的方法與基于鄰居覆蓋的概率轉(zhuǎn)發(fā)（Neighbor Coverage-based Probabilistic Rebroadcast，NCPR）廣播算法[19]和基于距離的多跳廣播（Distancebased Multi-hop Broadcast，DMB）算法[20]進(jìn)行比較，數(shù)據(jù)包生成率為10個(gè)/s，結(jié)果如圖8所示。

圖8 LLBR與NCPR、DMB的仿真結(jié)果

基于概率的廣播要求節(jié)點(diǎn)收到廣播數(shù)據(jù)包后以一定的概率P來(lái)轉(zhuǎn)發(fā)分組，其中P通常是由當(dāng)前節(jié)點(diǎn)到前一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)的距離與它們的傳輸范圍的比值決定的，則距離前一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)最遠(yuǎn)的節(jié)點(diǎn)最有可能成為新的中繼節(jié)點(diǎn)，當(dāng)P=1時(shí)，該方法等同于洪泛方法。當(dāng)車(chē)輛密度較大時(shí)，很多節(jié)點(diǎn)具有相似的覆蓋范圍，因此隨機(jī)使一些節(jié)點(diǎn)不再?gòu)V播分組在一定程度上節(jié)約了網(wǎng)絡(luò)資源。但是當(dāng)車(chē)輛密度較小時(shí)，節(jié)點(diǎn)間覆蓋范圍基本不重合，除非P足夠大，否則將會(huì)有一部分節(jié)點(diǎn)無(wú)法接收到所有廣播信息。基于概率的廣播的缺點(diǎn)是節(jié)點(diǎn)可能以較小或較大的概率來(lái)轉(zhuǎn)發(fā)分組，造成廣播分組的嚴(yán)重缺失或高度冗余。

基于距離的廣播算法在通信范圍內(nèi)節(jié)點(diǎn)間距離d越小則額外覆蓋面積越小，d越大則額外覆蓋面積就越大，當(dāng)d=0時(shí)，額外覆蓋面積也為0，該方法利用節(jié)點(diǎn)間的相對(duì)距離決定是否轉(zhuǎn)發(fā)分組，d可以通過(guò)GPS設(shè)備獲取或者根據(jù)消息的發(fā)射和接收功率間的關(guān)系計(jì)算得出。

由于車(chē)輛速度較快，車(chē)輛間的距離變化較快，所以基于距離的廣播算法性能較差。由圖8a可知：節(jié)點(diǎn)數(shù)量較少時(shí)，3種方法的數(shù)據(jù)包遞送率都接近1；當(dāng)區(qū)域中的節(jié)點(diǎn)數(shù)量增多時(shí)，DMB中數(shù)據(jù)包的遞送率下降明顯，NCPR算法較DMB算法表現(xiàn)更好，本文提出的廣播算法遞送率仍接近1。由圖8b可知：當(dāng)節(jié)點(diǎn)數(shù)量較少時(shí)，DMB和NCPR算法的平均端到端延時(shí)小于本文提出的廣播方法；隨著節(jié)點(diǎn)數(shù)量增多，DMB廣播產(chǎn)生的平均端到端延時(shí)增加明顯，而NCPR算法和本文所提出的方法有較好的性能。這是因?yàn)?，?dāng)節(jié)點(diǎn)數(shù)量較少時(shí)，網(wǎng)絡(luò)廣播的數(shù)據(jù)包較少，基本不會(huì)產(chǎn)生傳輸沖突，本文提出的廣播算法需要構(gòu)建CDS并計(jì)算支配集中節(jié)點(diǎn)的廣播概率，會(huì)產(chǎn)生延時(shí)；當(dāng)區(qū)域中的節(jié)點(diǎn)數(shù)量增多時(shí)，節(jié)點(diǎn)間相對(duì)距離減小，DMB算法的數(shù)據(jù)包數(shù)量增多，產(chǎn)生的沖突增多，造成重復(fù)廣播的次數(shù)增加，NCPR中，隨著節(jié)點(diǎn)數(shù)量的增加，對(duì)于相同的數(shù)據(jù)包來(lái)說(shuō)，其節(jié)點(diǎn)的鄰居節(jié)點(diǎn)的鄰居列表中該節(jié)點(diǎn)未覆蓋連通的節(jié)點(diǎn)（Uncovered Neighbors，UCN）集隨之減少，使得節(jié)點(diǎn)廣播該數(shù)據(jù)包的概率降低，即減少傳輸沖突，具有較好的延時(shí)，本文提出的廣播算法極大地減少了廣播的數(shù)據(jù)包數(shù)量和沖突的次數(shù)。

5 結(jié)束語(yǔ)

本文基于減少?gòu)V播數(shù)據(jù)包節(jié)點(diǎn)數(shù)量的思想設(shè)計(jì)廣播路由，對(duì)當(dāng)前節(jié)點(diǎn)通信范圍內(nèi)的節(jié)點(diǎn)構(gòu)建連通支配集，對(duì)連通支配集中的節(jié)點(diǎn)進(jìn)行數(shù)據(jù)包概率廣播，仿真結(jié)果表明，本文提出的方法極大地減少了廣播數(shù)據(jù)包的節(jié)點(diǎn)數(shù)和廣播時(shí)產(chǎn)生的沖突，從而減少數(shù)據(jù)包傳輸時(shí)的平均端到端延時(shí)，提高數(shù)據(jù)包的遞送率。