父節(jié)點(diǎn)可控的分布式纏繞多路徑路由算法*

劉庭緒，李志華

（江南大學(xué)物聯(lián)網(wǎng)工程學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系，江蘇無錫214122）

父節(jié)點(diǎn)可控的分布式纏繞多路徑路由算法*

劉庭緒，李志華*

（江南大學(xué)物聯(lián)網(wǎng)工程學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系，江蘇無錫214122）

針對(duì)無線傳感器網(wǎng)絡(luò)中無線鏈路存在因節(jié)點(diǎn)失效或傳輸介質(zhì)異構(gòu)容易引起傳輸可靠性降低的問題，提出提出父節(jié)點(diǎn)可控的分布式纏繞多路徑路由算法DPCBMR算法。該算法采用分層多父節(jié)點(diǎn)拓?fù)淇刂撇呗院蛥f(xié)作式數(shù)據(jù)轉(zhuǎn)發(fā)機(jī)制，在多跳轉(zhuǎn)發(fā)階段，引入最優(yōu)父節(jié)點(diǎn)選擇機(jī)制，根據(jù)轉(zhuǎn)發(fā)路徑上節(jié)點(diǎn)間的丟包率，選擇丟包率較低的多個(gè)節(jié)點(diǎn)作為轉(zhuǎn)發(fā)節(jié)點(diǎn)，以此來保證數(shù)據(jù)轉(zhuǎn)發(fā)的成功率；進(jìn)一步借助協(xié)作式數(shù)據(jù)轉(zhuǎn)發(fā)機(jī)制保證待轉(zhuǎn)發(fā)的數(shù)據(jù)在多路徑選擇時(shí)獲得最佳路徑，從而保證數(shù)據(jù)轉(zhuǎn)發(fā)的可靠性和低能量消耗。仿真實(shí)驗(yàn)結(jié)果表明DPCBMR算法能最大程度上提高數(shù)據(jù)傳輸?shù)目煽啃裕ＷC了數(shù)據(jù)傳輸?shù)某晒β?，同時(shí)降低了數(shù)據(jù)傳輸時(shí)的能量開銷。同經(jīng)典的SHM和CAMP算法相比較取得了比較大的改進(jìn)。

協(xié)作式傳輸；纏繞多路徑路由；最優(yōu)父節(jié)點(diǎn)選擇

EEACC：6150Pdoi：10.3969/j.issn.1004-1699.2016.09.021

因?yàn)槎嗦窂嚼p繞路由算法能快速地從失敗的路徑中重新找到正確的路由，近年來，受到了學(xué)術(shù)界和工業(yè)界的重視。文獻(xiàn)［1］對(duì)單路徑路由AODV進(jìn)行了擴(kuò)展，提出了目標(biāo)序列矢量多路徑路由算法AOMDV，AOMDV通過尋找出多條無環(huán)、鏈路不相交的路徑供失敗的路由快速、高效地恢復(fù)，但該算法在傳輸過程中只使用一條路徑，其他路徑作為備份路徑，一旦主路徑失敗，備份路由也無法保證數(shù)據(jù)傳輸?shù)某晒β?，使得路由發(fā)現(xiàn)的代價(jià)增加，降低了網(wǎng)絡(luò)性能；文獻(xiàn)［2］提出多路徑路由算法ReInForM，算法采用泛洪協(xié)議建立從源節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的多條路徑，該算法從數(shù)據(jù)源節(jié)點(diǎn)開始，考慮可靠性需求、信道質(zhì)量以及源節(jié)點(diǎn)到目的節(jié)點(diǎn)的跳數(shù)，決定需要的傳輸路徑數(shù)目，以及下一跳節(jié)點(diǎn)和相應(yīng)的節(jié)點(diǎn)數(shù)目，實(shí)現(xiàn)滿足可靠性要求的數(shù)據(jù)傳輸，雖然ReInForM路由算法能夠有效保證數(shù)據(jù)傳輸?shù)目煽啃?，但是在選取轉(zhuǎn)發(fā)節(jié)點(diǎn)時(shí)，僅追求單一的可靠性指標(biāo)，忽略了節(jié)點(diǎn)的負(fù)載均衡等問題；文獻(xiàn)［3］提出纏繞多路徑路由算法，用以解決從隨機(jī)節(jié)點(diǎn)故障中恢復(fù)的問題，使得主路徑上的故障恢復(fù)在少量路徑保持通暢的前提下能夠不依賴于泛洪廣播，但對(duì)于纏繞多路徑來說，如果主路徑和備用路徑存在相交的某一段路徑且這些相交路徑出現(xiàn)故障，經(jīng)過它們的主路徑和備用路徑同樣會(huì)失效。文獻(xiàn)［4］提出機(jī)會(huì)路由EXOR，采用逆向最短路徑算法計(jì)算各鄰居節(jié)點(diǎn)到目的節(jié)點(diǎn)的最小期望轉(zhuǎn)發(fā)總次數(shù)，并將其作為路由度量，在向節(jié)點(diǎn)發(fā)送數(shù)據(jù)前，源節(jié)點(diǎn)首先根據(jù)路由度量來選擇轉(zhuǎn)發(fā)候選節(jié)點(diǎn)集，并對(duì)轉(zhuǎn)發(fā)候選節(jié)點(diǎn)進(jìn)行優(yōu)先級(jí)排序，源節(jié)點(diǎn)發(fā)送數(shù)據(jù)包后，轉(zhuǎn)發(fā)候選節(jié)點(diǎn)按照優(yōu)先級(jí)從高到低的順序?qū)?shù)據(jù)包進(jìn)行轉(zhuǎn)發(fā)，直到目的節(jié)點(diǎn)收到所有的數(shù)據(jù)包，由于缺乏各備選轉(zhuǎn)發(fā)節(jié)點(diǎn)之間的有效相互確認(rèn)和協(xié)調(diào)機(jī)制，因此，目的節(jié)點(diǎn)所收到分組的重復(fù)率比較較高；文獻(xiàn)［5］提出了一種基于三角模算子的RPL協(xié)議路由優(yōu)化算法，該算法根據(jù)接收到的有向無環(huán)圖信息對(duì)象DIO（DODAG Information Object）消息，通過三角模融合算法選擇最優(yōu)父節(jié)點(diǎn)，有效均衡了網(wǎng)絡(luò)負(fù)載，延長了網(wǎng)絡(luò)生命周期，降低了能量損耗，但該算法中節(jié)點(diǎn)對(duì)周圍鄰居節(jié)點(diǎn)的鏈路信息獲取不完全，易造成節(jié)點(diǎn)所選擇的路徑并不是最優(yōu)路徑，導(dǎo)致算法的可靠性得不到保證；文獻(xiàn)［6-8］提出的算法將不相交多路徑路由與纏繞多路徑路由相結(jié)合，在數(shù)據(jù)進(jìn)行傳輸之前，建立多條纏繞多路徑，提高了數(shù)據(jù)傳輸?shù)目煽啃院蛯?shí)現(xiàn)了負(fù)載均衡，但同時(shí)也大大增加了各個(gè)節(jié)點(diǎn)的能量消耗，容易導(dǎo)致網(wǎng)絡(luò)能量的快速枯竭；文獻(xiàn)［9-11］提出的算法，在機(jī)會(huì)路由的基礎(chǔ)上，考慮無線鏈路的丟包率，加入節(jié)點(diǎn)間的協(xié)作式傳輸方法，無需知道節(jié)點(diǎn)的位置信息便可完成傳輸，提高了數(shù)據(jù)傳輸?shù)目煽啃?，降低了無線傳感器網(wǎng)絡(luò)的復(fù)雜性，但是算法僅選擇丟包率高于閾值的節(jié)點(diǎn)作為下一跳節(jié)點(diǎn)，使得算法只適用于密集型網(wǎng)絡(luò)，在網(wǎng)絡(luò)變得稀疏時(shí)，算法的性能將很難得到保證；文獻(xiàn)［12］提出了一種最小跳數(shù)多路徑算法SHM，采用廣度優(yōu)先搜索樹的策略建立纏繞多路徑路由，該算法利用迭代的方式，以最小跳數(shù)為基準(zhǔn)建立纏繞多路徑，網(wǎng)絡(luò)中的節(jié)點(diǎn)僅需保存上一層次節(jié)點(diǎn)信息，降低了無線傳感器網(wǎng)絡(luò)的復(fù)雜性，但該算法忽略了當(dāng)前節(jié)點(diǎn)的轉(zhuǎn)發(fā)節(jié)點(diǎn)集合規(guī)模，使得傳輸過程中因?yàn)檫^多或過少的上行節(jié)點(diǎn)導(dǎo)致數(shù)據(jù)包丟失或傳輸開銷大大增加；文獻(xiàn)［13］提出了一種基于網(wǎng)絡(luò)編碼的多路徑路由機(jī)制CAMP，該機(jī)制能夠根據(jù)路徑的可靠性和編碼機(jī)會(huì)，動(dòng)態(tài)地在多條路徑上進(jìn)行數(shù)據(jù)包的傳輸，CAMP的路由發(fā)現(xiàn)機(jī)制能夠向源節(jié)點(diǎn)返回多條可能的路徑以及各條路徑的每條邊上的期望傳輸次數(shù)ETX（Expected Transmis?sion Counts），可以通過轉(zhuǎn)換它的傳輸路徑來動(dòng)態(tài)地創(chuàng)造而非僅僅等待編碼機(jī)會(huì)，這使得CAMP可以讓多條路徑分?jǐn)偩W(wǎng)絡(luò)流量負(fù)載，并且最大化路徑轉(zhuǎn)換收益，從而改進(jìn)網(wǎng)絡(luò)的吞吐量，但CAMP算法對(duì)ETX的計(jì)算過于復(fù)雜，這將大幅度增加中間節(jié)點(diǎn)上的計(jì)算開銷從而增加傳輸時(shí)延。

候選節(jié)點(diǎn)集合進(jìn)行進(jìn)一步優(yōu)化選擇等不足，通過研究無線傳感器網(wǎng)絡(luò)的介質(zhì)特性，提出一種父節(jié)點(diǎn)可控的分布式纏繞多路徑路由DPCBMR（Distrib?uted Parents-controllable Braided Multipath Routing）算法。DPCBMR算法繼承了纏繞多路徑路由協(xié)作發(fā)送的特性和機(jī)會(huì)路由多點(diǎn)對(duì)一點(diǎn)的轉(zhuǎn)發(fā)思想，即節(jié)點(diǎn)只需要獲取網(wǎng)絡(luò)的局部拓?fù)湫畔⒓纯蛇M(jìn)行編碼操作，使算法能夠適用于節(jié)點(diǎn)分布不均勻的無線傳感器網(wǎng)絡(luò)。仿真實(shí)驗(yàn)表明DPCBMR算法在可靠性和傳輸開銷方面有比較好的表現(xiàn)。

1　網(wǎng)絡(luò)模型與假設(shè)

有一傳感器網(wǎng)絡(luò)，其中N個(gè)傳感器節(jié)點(diǎn)隨機(jī)分布在M×M區(qū)域內(nèi)，Sink節(jié)點(diǎn)處于M×M區(qū)域中的任意位置，假設(shè)如下：①Sink節(jié)點(diǎn)位置信息已知；②所有隨機(jī)分布的中間節(jié)點(diǎn)皆為靜態(tài)節(jié)點(diǎn)；③每一個(gè)節(jié)點(diǎn)有獨(dú)立的ID號(hào)和相同的收發(fā)能力；④每個(gè)節(jié)點(diǎn)通過周期性地向鄰居節(jié)點(diǎn)廣播探測(cè)包，獲取其鄰居節(jié)點(diǎn)ID并計(jì)算出自己與任意一個(gè)鄰居節(jié)點(diǎn)之間鏈路的丟包率；⑤無線傳感器網(wǎng)絡(luò)中的鏈路是雙向的，因此，路由應(yīng)答數(shù)據(jù)包可以沿著路由請(qǐng)求所發(fā)現(xiàn)的路徑原路返回；⑥在每個(gè)父節(jié)點(diǎn)上采取兩套同樣獨(dú)立配置的硬件系統(tǒng)，在其中一套系統(tǒng)出現(xiàn)故障時(shí)，另一套系統(tǒng)能立即啟動(dòng)，代替其工作。

2　DPCBMR算法

本節(jié)詳細(xì)介紹了DPCBMR算法的設(shè)計(jì)和實(shí)現(xiàn)細(xì)節(jié)。DPCBMR算法由分層多父節(jié)點(diǎn)拓?fù)錁?gòu)建算法，最優(yōu)父節(jié)點(diǎn)選擇算法，協(xié)作式數(shù)據(jù)傳輸算法3個(gè)子算法組成。以下依次說明DPCBMR算法的各個(gè)子算法。

2.1分層多父節(jié)點(diǎn)拓?fù)錁?gòu)建算法

文獻(xiàn)［14］指出有效的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)能夠?yàn)槠渌W(wǎng)絡(luò)服務(wù)支持技術(shù)提供基礎(chǔ)，提高網(wǎng)絡(luò)通信協(xié)議的應(yīng)用效率。通過分層多父節(jié)點(diǎn)拓?fù)浣Y(jié)構(gòu)構(gòu)建，每個(gè)節(jié)點(diǎn)都將獲取鄰居節(jié)點(diǎn)的信息，并確定轉(zhuǎn)發(fā)候選節(jié)點(diǎn)集合。分層多父節(jié)點(diǎn)拓?fù)浣Y(jié)構(gòu)是協(xié)作式數(shù)據(jù)發(fā)送得以實(shí)現(xiàn)的基礎(chǔ)。

在算法開始之前，網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)都需要對(duì)本身信息進(jìn)行初始化，初始化內(nèi)容包括節(jié)點(diǎn)ID、節(jié)點(diǎn)所在層次、父節(jié)點(diǎn)表、鄰居表以及子節(jié)點(diǎn)表等。

拓?fù)浣⒁酝降姆绞竭M(jìn)行，即以逐層鏈接確認(rèn)的方式進(jìn)行拓?fù)鋽U(kuò)展，形成分層的拓?fù)浣Y(jié)構(gòu)。算法中定義了四種消息格式，分別是：探測(cè)消息（probe）、探測(cè)應(yīng)答消息（ack）、層次更新消息（level update）以及層次更新應(yīng)答消息（lupack）。消息格式如表1所示。

表1　拓?fù)錁?gòu)建消息格式

探測(cè)消息是一個(gè)很小的鏈路層廣播數(shù)據(jù)包。網(wǎng)絡(luò)中的節(jié)點(diǎn)通過探測(cè)消息來確定自身所在層次。探測(cè)應(yīng)答消息是對(duì)探測(cè)消息的應(yīng)答消息，當(dāng)節(jié)點(diǎn)成功接收到探測(cè)消息并將發(fā)送節(jié)點(diǎn)設(shè)置為父節(jié)點(diǎn)后，便向發(fā)送節(jié)點(diǎn)回復(fù)一個(gè)探測(cè)應(yīng)答消息。層次更新消息由基站產(chǎn)生，用于通知相應(yīng)層次開始發(fā)送探測(cè)消息。層次更新應(yīng)答消息是對(duì)層次更新消息的應(yīng)答，該消息分為兩種形式，分別表示肯定（lupack）或否定（lupnack）答復(fù)，以標(biāo)志位Lupflag來區(qū)分，同時(shí)，該消息也是構(gòu)建過程完成的判定條件。

算法開始時(shí)基站將其層次設(shè)置為0，并將層次信息狀態(tài)以廣播的方式告知其鄰居節(jié)點(diǎn)。這些鄰居節(jié)點(diǎn)收到該廣播消息后，將自己的層次設(shè)置為1，并回復(fù)基站一個(gè)探測(cè)應(yīng)答消息。當(dāng)所有鄰居節(jié)點(diǎn)都將層次設(shè)置完畢后，基站開始廣播層次更新消息，接收到該消息的鄰居節(jié)點(diǎn)開始下一輪的層次更新，依次擴(kuò)展下去，最終全網(wǎng)范圍內(nèi)所有節(jié)點(diǎn)都獲得層次信息，算法終止。

算法的具體過程如算法1，描述如下。

2.2最優(yōu)父節(jié)點(diǎn)選擇算法

傳統(tǒng)的單路徑路由和多路徑路由機(jī)制中路徑需要由基站或者源節(jié)點(diǎn)確定，即中間節(jié)點(diǎn)的父節(jié)點(diǎn)將由基站或者源節(jié)點(diǎn)預(yù)先設(shè)定，在這一點(diǎn)上，DPCBMR算法區(qū)別于傳統(tǒng)算法的路由機(jī)制，父節(jié)點(diǎn)的個(gè)數(shù)將由節(jié)點(diǎn)本身計(jì)算得出。節(jié)點(diǎn)根據(jù)本身和它的鄰居之間的丟包率在當(dāng)前節(jié)點(diǎn)計(jì)算出所需父節(jié)點(diǎn)個(gè)數(shù)和選擇哪些節(jié)點(diǎn)作為父節(jié)點(diǎn)，以此來保證數(shù)據(jù)傳輸?shù)目煽啃?，降低?jì)算的復(fù)雜性。因此，通過上述過程使得纏繞多路徑路由上的每一跳的父節(jié)點(diǎn)個(gè)數(shù)可能不相同。

假設(shè)節(jié)點(diǎn)i與其鄰居節(jié)點(diǎn)j之間的丟包率為pij，其中1＜j＜Ni，Ni表示節(jié)點(diǎn)i的父節(jié)點(diǎn)個(gè)數(shù)，Pu表示節(jié)點(diǎn)u成功傳輸?shù)母怕?，hu表示源節(jié)點(diǎn)到目的節(jié)點(diǎn)所需的跳數(shù)，Pe表示數(shù)據(jù)成功傳輸?shù)母怕省２浑y看出，節(jié)點(diǎn)u成功傳輸?shù)母怕蕿椋?/p>

數(shù)據(jù)成功傳輸?shù)母怕蕿椋?/p>

為了保證數(shù)據(jù)傳輸?shù)某晒β什坏椭力襱，對(duì)于主路徑上單個(gè)節(jié)點(diǎn)u，成功傳輸?shù)母怕蕬?yīng)滿足式（3）：

進(jìn)一步，由式（2）可得：

在此，最優(yōu)父節(jié)點(diǎn)選擇算法選用如下策略，主路徑上的每一跳都獨(dú)立形成，即每一跳都由當(dāng)前節(jié)點(diǎn)選擇其父節(jié)點(diǎn)集合中丟包率較低的前幾個(gè)節(jié)點(diǎn)作為下一跳的發(fā)送節(jié)點(diǎn)并將父節(jié)點(diǎn)集合中丟包率最低的節(jié)點(diǎn)作為主路徑節(jié)點(diǎn)，其中主路徑節(jié)點(diǎn)根據(jù)式（3）從轉(zhuǎn)發(fā)候選節(jié)點(diǎn)集中選取父節(jié)點(diǎn)。

舉例說明如下，假設(shè)節(jié)點(diǎn)u的父節(jié)點(diǎn)集合為｛A，B，C，D｝，PuA=0.15，PuB=0.2，PuC=0.25，PuD=0.25。當(dāng)將設(shè)置為0.99時(shí)，選取父節(jié)點(diǎn)ABC，則Pu=1-0.15· 0.2·0.25=0.992 5＞0.99，即滿足要求。

最優(yōu)父節(jié)點(diǎn)算法的具體過程如算法2所示，描述如下。算法中Nu表示節(jié)點(diǎn)u的候選轉(zhuǎn)發(fā)節(jié)點(diǎn)集，myParents表示節(jié)點(diǎn)u的父節(jié)點(diǎn)集合。

2.3協(xié)作式數(shù)據(jù)轉(zhuǎn)發(fā)算法

本節(jié)將詳細(xì)描述協(xié)作式數(shù)據(jù)轉(zhuǎn)發(fā)算法的實(shí)現(xiàn)細(xì)節(jié)。在數(shù)據(jù)傳輸階段，源節(jié)點(diǎn)將數(shù)據(jù)包同時(shí)發(fā)送給多個(gè)節(jié)點(diǎn).這些節(jié)點(diǎn)都是通過最優(yōu)父節(jié)點(diǎn)選擇算法所選出的父節(jié)點(diǎn)。其應(yīng)用示例如圖1所示。

圖1　協(xié)作式傳輸應(yīng)用示例

傳統(tǒng)的單路徑路由和多路徑路由機(jī)制中所選擇的路徑都是某種標(biāo)準(zhǔn)下的最優(yōu)選項(xiàng)，但因?yàn)樗鼈兒鲆暳寺窂缴系钠渌麄鬏敊C(jī)會(huì)，使得系統(tǒng)的整體性能沒有被充分發(fā)揮出來。為了克服這個(gè)缺點(diǎn)，在此提出一種協(xié)作式數(shù)據(jù)轉(zhuǎn)發(fā)算法來充分利用路徑上的傳輸機(jī)會(huì)。

傳輸過程中使用的數(shù)據(jù)包格式如表2所示。

表2　傳輸數(shù)據(jù)包格式

協(xié)作式傳輸算法主要分為兩步：①源節(jié)點(diǎn)生成并廣播一個(gè)新的數(shù)據(jù)包；②接收到數(shù)據(jù)包的中間節(jié)點(diǎn)按協(xié)作式數(shù)據(jù)傳輸機(jī)制進(jìn)行傳輸。圖1中源節(jié)點(diǎn)1需要將數(shù)據(jù)包傳送到目的節(jié)點(diǎn)9，節(jié)點(diǎn)3、6、9分別是節(jié)點(diǎn)1、3、6的最優(yōu)父節(jié)點(diǎn)，則1、3、6、9為該傳輸過程的主路徑節(jié)點(diǎn)。在這個(gè)應(yīng)用場(chǎng)景中，節(jié)點(diǎn)1首先廣播一個(gè)數(shù)據(jù)包｛1，1，1，3，9，1，負(fù)載｝，該數(shù)據(jù)包將被節(jié)點(diǎn)2、3、4收到，節(jié)點(diǎn)3收到數(shù)據(jù)包后，發(fā)現(xiàn)主路徑標(biāo)志位為1，且它是發(fā)送節(jié)點(diǎn)1的父節(jié)點(diǎn)集合的首個(gè)節(jié)點(diǎn)，則它將廣播更新數(shù)據(jù)包｛1，1，3，6，9，1，負(fù)載｝。節(jié)點(diǎn)2收到來自節(jié)點(diǎn)1的數(shù)據(jù)包后，發(fā)現(xiàn)主路徑標(biāo)志位為1但它不是節(jié)點(diǎn)1的父節(jié)點(diǎn)集合的首個(gè)節(jié)點(diǎn)，則更新數(shù)據(jù)包中的發(fā)送節(jié)點(diǎn)ID、主路徑標(biāo)志位與主路徑ID為2、0、6，并將更新后的數(shù)據(jù)包｛1，0，2，6，9，1，負(fù)載｝廣播出去。節(jié)點(diǎn)4的情況與節(jié)點(diǎn)2類似。接著節(jié)點(diǎn)5、6、7、8將收到上述3個(gè)或其中部分?jǐn)?shù)據(jù)包，同節(jié)點(diǎn)2、3、4的情況相似，節(jié)點(diǎn)6作為節(jié)點(diǎn)3的最優(yōu)父節(jié)點(diǎn)將發(fā)送數(shù)據(jù)包｛1，1，6，9，9，1，負(fù)載｝，節(jié)點(diǎn)5、7將發(fā)送數(shù)據(jù)包｛1，0，5/7，9，9，1，負(fù)載｝。而節(jié)點(diǎn)8收到數(shù)據(jù)包后，發(fā)現(xiàn)主路徑標(biāo)志位不為1且節(jié)點(diǎn)3不在它的子節(jié)點(diǎn)集合中，則數(shù)據(jù)包將被丟棄。最后，基站將得到來自節(jié)點(diǎn)5、6和7的數(shù)據(jù)包。從上述例子可以看出，協(xié)作式數(shù)據(jù)傳輸算法的傳輸過程充分利用了每一跳的傳輸機(jī)會(huì)，且限制了路徑個(gè)數(shù)，保證可靠性的同時(shí)，也減少了傳輸開銷。

協(xié)作式數(shù)據(jù)傳輸算法如算法3所示，其具體實(shí)現(xiàn)過程描述如下：

3　算法分析

3.1消息復(fù)雜度

假設(shè)L是無線傳感器網(wǎng)路的最大層次數(shù)，Qi表示i層所包含的總節(jié)點(diǎn)數(shù)，qi表示第i層所含的節(jié)點(diǎn)數(shù)。建立拓?fù)浣Y(jié)構(gòu)階段，每向下更新一層，對(duì)應(yīng)層次上的節(jié)點(diǎn)將發(fā)送并接收1次探測(cè)和探測(cè)應(yīng)答消息，而中間層次上的節(jié)點(diǎn)都將發(fā)送一次層次更新和層次更新應(yīng)答消息。則當(dāng)0＜i≤L時(shí)，構(gòu)建i層拓?fù)浣Y(jié)構(gòu)的消息復(fù)雜度為：

則全網(wǎng)構(gòu)建拓?fù)浣Y(jié)構(gòu)的消息復(fù)雜度為：

數(shù)據(jù)傳輸階段，發(fā)送的消息次數(shù)由丟包率與主路徑節(jié)點(diǎn)的父節(jié)點(diǎn)個(gè)數(shù)決定，將在3.4節(jié)給出詳細(xì)的證明過程，假設(shè)主路徑上第i個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)個(gè)數(shù)為Mi，則每向上傳輸一次數(shù)據(jù)包，將有Mi個(gè)節(jié)點(diǎn)接收并發(fā)送數(shù)據(jù)包。則數(shù)據(jù)傳輸?shù)南?fù)雜度為：

將兩個(gè)階段的消息復(fù)雜度相加得到算法的消息復(fù)雜度為：

3.2時(shí)間復(fù)雜度

建立拓?fù)浣Y(jié)構(gòu)階段，發(fā)送更新和層次更新應(yīng)答消息階段將消耗2i個(gè)單位時(shí)間，而發(fā)送探測(cè)與接收探測(cè)應(yīng)答消息將消耗額外2個(gè)單位時(shí)間。則當(dāng)0＜i≤L時(shí)，構(gòu)建i層拓?fù)浣Y(jié)構(gòu)的時(shí)間復(fù)雜度為：

數(shù)據(jù)傳輸階段，數(shù)據(jù)包的傳輸將消耗i個(gè)單位時(shí)間。則當(dāng)0＜i≤L時(shí)，數(shù)據(jù)傳輸?shù)臅r(shí)間復(fù)雜度為：

將兩個(gè)階段的時(shí)間復(fù)雜度相加得到算法的時(shí)間復(fù)雜度為：

3.3可靠性分析

DPCBMR算法的實(shí)現(xiàn)不是一個(gè)簡單的過程，首先通過最優(yōu)父節(jié)點(diǎn)的選擇，DPCBMR算法可以充分獲得傳輸路徑上的傳輸機(jī)會(huì)，以此為數(shù)據(jù)的高效傳輸?shù)於ɑA(chǔ)。本節(jié)將對(duì)DPCBMR算法的可靠性進(jìn)行理論分析。

通過分析最好與最壞的情況，可以獲得DPCBMR算法的可靠性上下界。在最好的情況時(shí)，相鄰節(jié)點(diǎn)總是能夠成功連接，即即使只有一條路徑，也能夠完成數(shù)據(jù)傳輸。最壞的情況下，只有主路徑上的節(jié)點(diǎn)是可以成功連接的，即整個(gè)傳輸過程的可靠性都要由主路徑來保證。假設(shè)從源節(jié)點(diǎn)到基站之間存在h跳，主路徑上第i個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)個(gè)數(shù)為Mi，p1為該路徑上節(jié)點(diǎn)失效的概率，p2為鏈路失效的概率。

①考慮節(jié)點(diǎn)失效的情況，每一跳至少存在一個(gè)節(jié)點(diǎn)不會(huì)失效，才能保證傳輸成功。假設(shè)源節(jié)點(diǎn)和基站永遠(yuǎn)不會(huì)失效。在最好的情況下，每一跳的成功傳輸概率為，則DPCBMR算法的可靠性上界可表示為：

最壞情況下，僅主路徑上節(jié)點(diǎn)可以成功連接，因此每一跳的成功傳輸概率為1-p1，為了保證傳輸成功，主路徑上的每一個(gè)節(jié)點(diǎn)都不能失效，所以DPCBMR算法的可靠性下界可表示為：

考慮鏈路失效的情況，最好的情況下，第i跳存在的鏈路數(shù)為：

為了保證下一跳上有節(jié)點(diǎn)能夠接收到數(shù)據(jù)包，每一跳至少有一條鏈路能夠成功連接，而每一跳的成功傳輸概率為因此在此種情況下，傳輸成功概率的上界為：

最壞的情況下，主路徑上的鏈接都不能失效，數(shù)據(jù)包才能成功傳輸?shù)侥康墓?jié)點(diǎn)，所以傳輸成功的概率下界為：

可見，DPCBMR算法的可靠性會(huì)隨著傳輸路徑上傳輸機(jī)會(huì)的增加而逐漸提高。

3.4傳輸開銷

在無線傳感器網(wǎng)絡(luò)中，開銷主要涉及傳輸開銷、計(jì)算開銷與存儲(chǔ)開銷3部分。由于計(jì)算與存儲(chǔ)開銷較低，本文只考慮傳輸開銷，而消息的傳輸次數(shù)能很好的反應(yīng)無線傳感器網(wǎng)絡(luò)中的傳輸開銷，所以本節(jié)將對(duì)DPCBMR算法的傳輸次數(shù)進(jìn)行分析，從這個(gè)側(cè)面來間接地表示傳輸開銷。

與上節(jié)的分析過程相同，DPCBMR算法的傳輸次數(shù)也從最好與最壞兩個(gè)角度進(jìn)行分析。在最好情況下，相鄰跳之間的成對(duì)節(jié)點(diǎn)始終是連通的。而第i跳上的子節(jié)點(diǎn)個(gè)數(shù)可由式（17）表示：

假設(shè)鏈路的丟包率為pe，Ti表示第i跳上的發(fā)送次數(shù)，Ci是在第i跳上成功接收并轉(zhuǎn)發(fā)數(shù)據(jù)包的父節(jié)點(diǎn)的個(gè)數(shù)，對(duì)應(yīng)于i-1跳中j個(gè)成功連接的鏈路。則表示每個(gè)節(jié)點(diǎn)的平均鏈路個(gè)數(shù)可由下式求得：

由于第i跳上最多有Mi個(gè)節(jié)點(diǎn)參與傳輸，即第i跳上的每個(gè)子節(jié)點(diǎn)最多與Mi個(gè)父節(jié)點(diǎn)組成Mi條鏈路，所以

在最好的情況下，網(wǎng)絡(luò)中每條鏈路都是連通的，顯然，第一跳僅由源節(jié)點(diǎn)發(fā)送數(shù)據(jù)包，所以，T1=1，第二跳僅僅是源節(jié)點(diǎn)的父節(jié)點(diǎn)可能接受并轉(zhuǎn)發(fā)數(shù)據(jù)包，所以，同樣，當(dāng)2＜i≤h時(shí)，第i跳上僅第i-1跳上的父節(jié)點(diǎn)可能接收并轉(zhuǎn)發(fā)數(shù)據(jù)包，因此可得：

取Ci的最大值Mi，并帶入式（19）得到發(fā)送次數(shù)的上界為：

同樣，在最壞的情況下，僅僅有主路徑上相鄰跳之間的節(jié)點(diǎn)可以成功連接，所以，當(dāng)2＜i≤h時(shí)：

因此傳輸次數(shù)的下界為：

4　實(shí)驗(yàn)分析

為了驗(yàn)證父節(jié)點(diǎn)可控的DPCBMR算法的性能，本文使用java實(shí)現(xiàn)了DPCBMR、SHM以及CAMP算法并對(duì)它們進(jìn)行比較。實(shí)驗(yàn)中節(jié)點(diǎn)隨機(jī)分布在200×200的范圍內(nèi)。

實(shí)驗(yàn)1實(shí)驗(yàn)1主要研究跳數(shù)Hops對(duì)傳輸可靠性的影響。

在200×200的場(chǎng)景中，隨機(jī)分布600個(gè)節(jié)點(diǎn)，傳輸半徑為15，選擇距基站跳數(shù)為1到10的10個(gè)節(jié)點(diǎn)，進(jìn)行仿真實(shí)驗(yàn)，每組分別對(duì)3種算法進(jìn)行100次實(shí)驗(yàn)，取其平均值作為實(shí)驗(yàn)結(jié)果，實(shí)驗(yàn)結(jié)果如圖2所示。

圖2　不同跳數(shù)情況下的成功率及傳輸次數(shù)

在圖2（a）中，3種算法隨著跳數(shù)的增加，成功率都呈下降趨勢(shì)，DPCBMR算法，成功率一直保持在80%以上，在成功率方面比SHM高出20%～28%，比CAMP高出30%～41%，對(duì)應(yīng)于其他兩種算法更具優(yōu)勢(shì)。圖中第7跳，SHM與CAMP的可靠性突然增長，這是由于選擇的第七跳節(jié)點(diǎn)處于節(jié)點(diǎn)分布較為密集的部分，使得SHM與CAMP的傳輸機(jī)會(huì)大大增加。同時(shí)，由于SHM算法在傳輸過程中僅選擇跳數(shù)最少的節(jié)點(diǎn)，并沒有考慮丟包率，使得該算法隨著跳數(shù)的增加，性能有所下降。圖2（b）中，三種算法隨著跳數(shù)的增加，傳輸開銷都呈增長趨勢(shì)，本文提出的算法傳輸開銷方面比SHM低12%～25%，比CAMP高出11%～38%，這是由于CAMP除源節(jié)點(diǎn)外，所有中間節(jié)點(diǎn)都僅會(huì)選擇性能最優(yōu)的節(jié)點(diǎn)作為下一跳節(jié)點(diǎn)，使得其傳輸開銷較小，而SHM并未對(duì)候選轉(zhuǎn)發(fā)節(jié)點(diǎn)集合的大小進(jìn)行限制，保證成功率的同時(shí)也大大增加了開銷。DPCBMR算法在選擇下一跳節(jié)點(diǎn)時(shí)同時(shí)考慮到可靠性和能耗需求，僅選擇候選轉(zhuǎn)發(fā)集合中的前N個(gè)節(jié)點(diǎn)作為下行節(jié)點(diǎn)，所以，相比較之下，DPCBMR算法很大程度上提高了數(shù)據(jù)傳輸?shù)目煽啃浴?/p>

實(shí)驗(yàn)2 實(shí)驗(yàn)2的主要目的是為了評(píng)價(jià)DP?CBMR算法在抗丟包率干擾的能力。

在200×200的場(chǎng)景中，隨機(jī)分布600個(gè)節(jié)點(diǎn)，傳輸半徑15，選擇距離基站跳數(shù)為10的節(jié)點(diǎn)進(jìn)行傳輸實(shí)驗(yàn)，選擇丟包率0.10～0.55，實(shí)驗(yàn)結(jié)果如圖3所示。從圖3可以看出PCMR算法在丟包率高于0.35的情況下都比其它兩種算法轉(zhuǎn)發(fā)成功率高，即大多數(shù)情況下數(shù)據(jù)包能夠到達(dá)目的節(jié)點(diǎn)。雖然CAMP堅(jiān)持使用期望最好的無線鏈路轉(zhuǎn)發(fā)數(shù)據(jù)包，然而在WSNs中，即使最好的無線鏈路也有失效的時(shí)候，這使得CAMP算法極易失效。DPCBMR算法通過最優(yōu)父節(jié)點(diǎn)選擇，從大量候選鄰居節(jié)點(diǎn)中選擇當(dāng)時(shí)最好的幾個(gè)節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)包，能夠有效回避丟包率較高的鏈路。其次，DPCBMR算法獲得的轉(zhuǎn)發(fā)成功率結(jié)果下降趨勢(shì)更加平穩(wěn)。雖然特定的無線鏈路在不同時(shí)刻可能表現(xiàn)出極大的性能差異，但是DPCBMR算法能夠利用比較“優(yōu)”的鏈路，以規(guī)避“差”的鏈路，因此在整個(gè)路由路徑上得到的轉(zhuǎn)發(fā)成功率結(jié)果相對(duì)穩(wěn)定。

圖3　不同丟包率情況下的成功率

實(shí)驗(yàn)3實(shí)驗(yàn)3的主要目的是為了評(píng)價(jià)DPCBMR算法在不同節(jié)點(diǎn)密度下的性能。

在200×200的場(chǎng)景中，傳輸半徑15，選擇距離基站跳數(shù)為10的節(jié)點(diǎn)進(jìn)行傳輸實(shí)驗(yàn)，改變節(jié)點(diǎn)數(shù)量從300到600。在每個(gè)場(chǎng)景下，進(jìn)行100次仿真，并使用平均值進(jìn)行比較。仿真結(jié)果如圖4所示。由于拓?fù)浣Y(jié)構(gòu)是隨機(jī)生成的，各個(gè)拓?fù)淇赡苡胁煌男再|(zhì)，這使得實(shí)驗(yàn)結(jié)果會(huì)有所波動(dòng)。如圖4（a）中所示，DPCBMR算法在轉(zhuǎn)發(fā)成功率方面比SHM高出20%～28%，比CAMP高出30%～41%，相比其他兩種算法更能適應(yīng)于不同的網(wǎng)絡(luò)環(huán)境。在圖4（b）中，隨著節(jié)點(diǎn)密度的增大，SHM的傳輸開銷急劇增加，這是由于發(fā)送列表增大，導(dǎo)致鏈路個(gè)數(shù)成倍增長所造成的。而本文提出的算法的傳輸開銷同樣隨之增加，這是由于隨著節(jié)點(diǎn)密度的增大，每一跳上的節(jié)點(diǎn)都能選擇足夠的父節(jié)點(diǎn)作為發(fā)送節(jié)點(diǎn)，但隨著節(jié)點(diǎn)密度繼續(xù)增大，每一跳上的節(jié)點(diǎn)將不再選取額外的父節(jié)點(diǎn)，傳輸開銷也將趨于平緩。

圖4　不同節(jié)點(diǎn)數(shù)情況下的轉(zhuǎn)發(fā)成功率及傳輸次數(shù)

5　結(jié)論

本文對(duì)無線傳感器網(wǎng)絡(luò)中現(xiàn)有的路由算法進(jìn)行了分析，在此基礎(chǔ)上，提出父節(jié)點(diǎn)可控的分布式纏繞多路徑路由DPCBMR算法，該算法在保證了高傳輸可靠性的同時(shí)，減少了傳輸開銷，這一特性對(duì)丟包率較高的無線傳感器網(wǎng)絡(luò)應(yīng)用場(chǎng)合來說非常有意義，具有一定的實(shí)用價(jià)值。但DPCBMR算法暫時(shí)適用于靜態(tài)網(wǎng)絡(luò)，并未考慮無線傳感網(wǎng)的可擴(kuò)展性特征，即在一旦有新的傳感器節(jié)點(diǎn)加入網(wǎng)絡(luò)后將需要新的拓?fù)錁?gòu)建過程，這將是我們下一步的研究重點(diǎn)。

［1］Marina M K，Das S R.Ad Hoc on-Demand Multipath Distance Vector Routing［J］.Wireless Communications&Mobile Comput?ing，2006，6（7）：969-988.

［2］Tarique M，Tepe K E，Adibi S，et al.Survey of Multipath Routing Protocols for Mobile Ad Hoc Networks［J］.Journal of Network& Computer Applications，2009，32（6）：1125-1143.

［3］Deb B，Bhatnagar S，Nath B.ReInForM：Reliable Information For?warding Using Multiple Paths in Sensor Networks［C］//Local Com?puter Networks，2003.LCN’03.Proceedings.28th Annual IEEE International Conference on，2003：406-415.

［4］Biswas S，Morris R.ExOR：Opportunistic Multi-Hop Routing for Wireless Networks［M］.ACM，2005：133-144.

［5］仇英輝，何霖.基于三角模算子的RPL協(xié)議路由優(yōu)化算法［J］.傳感技術(shù)學(xué)報(bào)，2015，（12）：1861-1866.

［6］Lou W，Kwon Y.H-SPREAD：A Hybrid Multipath Scheme for Se?cure and Reliable Data Collection in Wireless Sensor Networks［J］.IEEE Transactions on Vehicular Technology，2006，55（4）：1320-1330.

［7］Elhawary M，Haas Z J.Energy-Efficient Protocol for Cooperative Networks［J］.IEEE/ACM Transactions on Networking，2011，19（2）：561-574.

［8］Yang Y，Zhong C，Sun Y，et al.Network Coding Based Reliable Dis?joint and Braided Multipath Routing for Sensor Networks［J］.Jour?nal of Network&Computer Applications，2010，33（4）：422-432.

［9］Keller L，Atsan E，Argyraki K，et al.Sense Code：Network Coding for Reliable Sensor Networks［J］.Acm Transactions on Sensor Networks，2013，9（2）：53-55.

［10］Xu M，Song W Z，Zhao Y.Collaborative Data Collection with Op?portunistic Network Erasure Coding［J］.IEEE Transactions on Parallel&Distributed Systems，2013，24（10）：1941-1950.

［11］Niu J，Cheng L，Gu Y，et al.R3E：Reliable Reactive Routing En?hancement for Wireless Sensor Networks［J］.IEEE Transactions on Industrial Informatics，2014，10（1）：784-794.

［12］Yilmaz O，Demirci S，Kaymak Y，et al.Shortest Hop Multipath Al?gorithm for Wireless Sensor Networks［J］.Computers&Mathemat?ics with Applications，2012，63（1）：48-59.

［13］陳貴海，李宏興，韓松，等.多跳無線網(wǎng)絡(luò)中基于網(wǎng)絡(luò)編碼的多路徑路由［J］.軟件學(xué)報(bào)，2010，21（8）：1908-1919.

［14］聶云峰，王長勝，陳崇毅，等.一種空間查詢高效的無線傳感網(wǎng)絡(luò)路由協(xié)議［J］.傳感技術(shù)學(xué)報(bào)，2015，（5）：744-751.

劉庭緒（1989-），男，安徽黃山人，碩士研究生，研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)，zhaji2005@163.com；

李志華（1969-），男，湖南保靖人，博士，教授，碩士生導(dǎo)師，研究方向?yàn)榫W(wǎng)絡(luò)技術(shù)、信息安全、數(shù)據(jù)挖掘等，ezhli@aliyun.com。

Distributed Parents-Controllable Braided Multipath Routing Algorithm*

LIU Tingxu，LI Zhihua*
（Department of Computer Science，School of Internet of Things Engineering，Jiangnan University，Wuxi Jiangsu 214122，China）

To solve the problem of low reliability which appears in dynamic and heterogeneous wireless communica?tion link，this paper proposes a Distributed Parents-Controllable Braided Multipath Routing（DPCBMR）algorithm.DPCBMR employs the hierarchical multi-parents control strategy and cooperation packet deliverying strategy dur?ing the procedure of multi-hop forwarding and selection paths.The multi-parents control strategy is inspired to se?lect the nodes with less packet loss ratio as the forwarding nodes，and the cooperation packet deliverying strategy helps to select the next hop in the multi-paths with higher transmission reliability while as less energy consumption.Experimental results show that the DPCBMR can achieve more higher reliability，more efficient transmission ratio while keeping less energy consumption compared with the typical SHM and CAMP algorithm.

cooperation packet deliverying；braided multipath；optimal parent nodes selection

TP393

A

1004-1699（2016）09-1416-09

項(xiàng)目來源：中央科研專項(xiàng)基金項(xiàng)目（JUSRP211A41）；江蘇省科技廳產(chǎn)學(xué)研前瞻基金項(xiàng)目（BY2013015-23）

2016-02-26修改日期：2016-04-06