父節點可控的分布式纏繞多路徑路由算法*

劉庭緒，李志華

（江南大學物聯網工程學院計算機科學與技術系，江蘇無錫214122）

父節點可控的分布式纏繞多路徑路由算法*

劉庭緒，李志華*

（江南大學物聯網工程學院計算機科學與技術系，江蘇無錫214122）

針對無線傳感器網絡中無線鏈路存在因節點失效或傳輸介質異構容易引起傳輸可靠性降低的問題，提出提出父節點可控的分布式纏繞多路徑路由算法DPCBMR算法。該算法采用分層多父節點拓撲控制策略和協作式數據轉發機制，在多跳轉發階段，引入最優父節點選擇機制，根據轉發路徑上節點間的丟包率，選擇丟包率較低的多個節點作為轉發節點，以此來保證數據轉發的成功率；進一步借助協作式數據轉發機制保證待轉發的數據在多路徑選擇時獲得最佳路徑，從而保證數據轉發的可靠性和低能量消耗。仿真實驗結果表明DPCBMR算法能最大程度上提高數據傳輸的可靠性，保證了數據傳輸的成功率，同時降低了數據傳輸時的能量開銷。同經典的SHM和CAMP算法相比較取得了比較大的改進。

協作式傳輸；纏繞多路徑路由；最優父節點選擇

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

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

候選節點集合進行進一步優化選擇等不足，通過研究無線傳感器網絡的介質特性，提出一種父節點可控的分布式纏繞多路徑路由DPCBMR（Distrib?uted Parents-controllable Braided Multipath Routing）算法。DPCBMR算法繼承了纏繞多路徑路由協作發送的特性和機會路由多點對一點的轉發思想，即節點只需要獲取網絡的局部拓撲信息即可進行編碼操作，使算法能夠適用于節點分布不均勻的無線傳感器網絡。仿真實驗表明DPCBMR算法在可靠性和傳輸開銷方面有比較好的表現。

1　網絡模型與假設

有一傳感器網絡，其中N個傳感器節點隨機分布在M×M區域內，Sink節點處于M×M區域中的任意位置，假設如下：①Sink節點位置信息已知；②所有隨機分布的中間節點皆為靜態節點；③每一個節點有獨立的ID號和相同的收發能力；④每個節點通過周期性地向鄰居節點廣播探測包，獲取其鄰居節點ID并計算出自己與任意一個鄰居節點之間鏈路的丟包率；⑤無線傳感器網絡中的鏈路是雙向的，因此，路由應答數據包可以沿著路由請求所發現的路徑原路返回；⑥在每個父節點上采取兩套同樣獨立配置的硬件系統，在其中一套系統出現故障時，另一套系統能立即啟動，代替其工作。

2　DPCBMR算法

本節詳細介紹了DPCBMR算法的設計和實現細節。DPCBMR算法由分層多父節點拓撲構建算法，最優父節點選擇算法，協作式數據傳輸算法3個子算法組成。以下依次說明DPCBMR算法的各個子算法。

2.1分層多父節點拓撲構建算法

文獻［14］指出有效的網絡拓撲結構能夠為其他網絡服務支持技術提供基礎，提高網絡通信協議的應用效率。通過分層多父節點拓撲結構構建，每個節點都將獲取鄰居節點的信息，并確定轉發候選節點集合。分層多父節點拓撲結構是協作式數據發送得以實現的基礎。

在算法開始之前，網絡中的每個節點都需要對本身信息進行初始化，初始化內容包括節點ID、節點所在層次、父節點表、鄰居表以及子節點表等。

拓撲建立以同步的方式進行，即以逐層鏈接確認的方式進行拓撲擴展，形成分層的拓撲結構。算法中定義了四種消息格式，分別是：探測消息（probe）、探測應答消息（ack）、層次更新消息（level update）以及層次更新應答消息（lupack）。消息格式如表1所示。

表1　拓撲構建消息格式

探測消息是一個很小的鏈路層廣播數據包。網絡中的節點通過探測消息來確定自身所在層次。探測應答消息是對探測消息的應答消息，當節點成功接收到探測消息并將發送節點設置為父節點后，便向發送節點回復一個探測應答消息。層次更新消息由基站產生，用于通知相應層次開始發送探測消息。層次更新應答消息是對層次更新消息的應答，該消息分為兩種形式，分別表示肯定（lupack）或否定（lupnack）答復，以標志位Lupflag來區分，同時，該消息也是構建過程完成的判定條件。

算法開始時基站將其層次設置為0，并將層次信息狀態以廣播的方式告知其鄰居節點。這些鄰居節點收到該廣播消息后，將自己的層次設置為1，并回復基站一個探測應答消息。當所有鄰居節點都將層次設置完畢后，基站開始廣播層次更新消息，接收到該消息的鄰居節點開始下一輪的層次更新，依次擴展下去，最終全網范圍內所有節點都獲得層次信息，算法終止。

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

2.2最優父節點選擇算法

傳統的單路徑路由和多路徑路由機制中路徑需要由基站或者源節點確定，即中間節點的父節點將由基站或者源節點預先設定，在這一點上，DPCBMR算法區別于傳統算法的路由機制，父節點的個數將由節點本身計算得出。節點根據本身和它的鄰居之間的丟包率在當前節點計算出所需父節點個數和選擇哪些節點作為父節點，以此來保證數據傳輸的可靠性，降低計算的復雜性。因此，通過上述過程使得纏繞多路徑路由上的每一跳的父節點個數可能不相同。

假設節點i與其鄰居節點j之間的丟包率為pij，其中1＜j＜Ni，Ni表示節點i的父節點個數，Pu表示節點u成功傳輸的概率，hu表示源節點到目的節點所需的跳數，Pe表示數據成功傳輸的概率。不難看出，節點u成功傳輸的概率為：

數據成功傳輸的概率為：

為了保證數據傳輸的成功率不低至σt，對于主路徑上單個節點u，成功傳輸的概率應滿足式（3）：

進一步，由式（2）可得：

在此，最優父節點選擇算法選用如下策略，主路徑上的每一跳都獨立形成，即每一跳都由當前節點選擇其父節點集合中丟包率較低的前幾個節點作為下一跳的發送節點并將父節點集合中丟包率最低的節點作為主路徑節點，其中主路徑節點根據式（3）從轉發候選節點集中選取父節點。

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

最優父節點算法的具體過程如算法2所示，描述如下。算法中Nu表示節點u的候選轉發節點集，myParents表示節點u的父節點集合。

2.3協作式數據轉發算法

本節將詳細描述協作式數據轉發算法的實現細節。在數據傳輸階段，源節點將數據包同時發送給多個節點.這些節點都是通過最優父節點選擇算法所選出的父節點。其應用示例如圖1所示。

圖1　協作式傳輸應用示例

傳統的單路徑路由和多路徑路由機制中所選擇的路徑都是某種標準下的最優選項，但因為它們忽視了路徑上的其他傳輸機會，使得系統的整體性能沒有被充分發揮出來。為了克服這個缺點，在此提出一種協作式數據轉發算法來充分利用路徑上的傳輸機會。

傳輸過程中使用的數據包格式如表2所示。

表2　傳輸數據包格式

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

協作式數據傳輸算法如算法3所示，其具體實現過程描述如下：

3　算法分析

3.1消息復雜度

假設L是無線傳感器網路的最大層次數，Qi表示i層所包含的總節點數，qi表示第i層所含的節點數。建立拓撲結構階段，每向下更新一層，對應層次上的節點將發送并接收1次探測和探測應答消息，而中間層次上的節點都將發送一次層次更新和層次更新應答消息。則當0＜i≤L時，構建i層拓撲結構的消息復雜度為：

則全網構建拓撲結構的消息復雜度為：

數據傳輸階段，發送的消息次數由丟包率與主路徑節點的父節點個數決定，將在3.4節給出詳細的證明過程，假設主路徑上第i個節點的父節點個數為Mi，則每向上傳輸一次數據包，將有Mi個節點接收并發送數據包。則數據傳輸的消息復雜度為：

將兩個階段的消息復雜度相加得到算法的消息復雜度為：

3.2時間復雜度

建立拓撲結構階段，發送更新和層次更新應答消息階段將消耗2i個單位時間，而發送探測與接收探測應答消息將消耗額外2個單位時間。則當0＜i≤L時，構建i層拓撲結構的時間復雜度為：

數據傳輸階段，數據包的傳輸將消耗i個單位時間。則當0＜i≤L時，數據傳輸的時間復雜度為：

將兩個階段的時間復雜度相加得到算法的時間復雜度為：

3.3可靠性分析

DPCBMR算法的實現不是一個簡單的過程，首先通過最優父節點的選擇，DPCBMR算法可以充分獲得傳輸路徑上的傳輸機會，以此為數據的高效傳輸奠定基礎。本節將對DPCBMR算法的可靠性進行理論分析。

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

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

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

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

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

最壞的情況下，主路徑上的鏈接都不能失效，數據包才能成功傳輸到目的節點，所以傳輸成功的概率下界為：

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

3.4傳輸開銷

在無線傳感器網絡中，開銷主要涉及傳輸開銷、計算開銷與存儲開銷3部分。由于計算與存儲開銷較低，本文只考慮傳輸開銷，而消息的傳輸次數能很好的反應無線傳感器網絡中的傳輸開銷，所以本節將對DPCBMR算法的傳輸次數進行分析，從這個側面來間接地表示傳輸開銷。

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

假設鏈路的丟包率為pe，Ti表示第i跳上的發送次數，Ci是在第i跳上成功接收并轉發數據包的父節點的個數，對應于i-1跳中j個成功連接的鏈路。則表示每個節點的平均鏈路個數可由下式求得：

由于第i跳上最多有Mi個節點參與傳輸，即第i跳上的每個子節點最多與Mi個父節點組成Mi條鏈路，所以

在最好的情況下，網絡中每條鏈路都是連通的，顯然，第一跳僅由源節點發送數據包，所以，T1=1，第二跳僅僅是源節點的父節點可能接受并轉發數據包，所以，同樣，當2＜i≤h時，第i跳上僅第i-1跳上的父節點可能接收并轉發數據包，因此可得：

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

同樣，在最壞的情況下，僅僅有主路徑上相鄰跳之間的節點可以成功連接，所以，當2＜i≤h時：

因此傳輸次數的下界為：

4　實驗分析

為了驗證父節點可控的DPCBMR算法的性能，本文使用java實現了DPCBMR、SHM以及CAMP算法并對它們進行比較。實驗中節點隨機分布在200×200的范圍內。

實驗1實驗1主要研究跳數Hops對傳輸可靠性的影響。

在200×200的場景中，隨機分布600個節點，傳輸半徑為15，選擇距基站跳數為1到10的10個節點，進行仿真實驗，每組分別對3種算法進行100次實驗，取其平均值作為實驗結果，實驗結果如圖2所示。

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

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

實驗2 實驗2的主要目的是為了評價DP?CBMR算法在抗丟包率干擾的能力。

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

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

實驗3實驗3的主要目的是為了評價DPCBMR算法在不同節點密度下的性能。

在200×200的場景中，傳輸半徑15，選擇距離基站跳數為10的節點進行傳輸實驗，改變節點數量從300到600。在每個場景下，進行100次仿真，并使用平均值進行比較。仿真結果如圖4所示。由于拓撲結構是隨機生成的，各個拓撲可能有不同的性質，這使得實驗結果會有所波動。如圖4（a）中所示，DPCBMR算法在轉發成功率方面比SHM高出20%～28%，比CAMP高出30%～41%，相比其他兩種算法更能適應于不同的網絡環境。在圖4（b）中，隨著節點密度的增大，SHM的傳輸開銷急劇增加，這是由于發送列表增大，導致鏈路個數成倍增長所造成的。而本文提出的算法的傳輸開銷同樣隨之增加，這是由于隨著節點密度的增大，每一跳上的節點都能選擇足夠的父節點作為發送節點，但隨著節點密度繼續增大，每一跳上的節點將不再選取額外的父節點，傳輸開銷也將趨于平緩。

圖4　不同節點數情況下的轉發成功率及傳輸次數

5　結論

本文對無線傳感器網絡中現有的路由算法進行了分析，在此基礎上，提出父節點可控的分布式纏繞多路徑路由DPCBMR算法，該算法在保證了高傳輸可靠性的同時，減少了傳輸開銷，這一特性對丟包率較高的無線傳感器網絡應用場合來說非常有意義，具有一定的實用價值。但DPCBMR算法暫時適用于靜態網絡，并未考慮無線傳感網的可擴展性特征，即在一旦有新的傳感器節點加入網絡后將需要新的拓撲構建過程，這將是我們下一步的研究重點。

［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協議路由優化算法［J］.傳感技術學報，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］陳貴海，李宏興，韓松，等.多跳無線網絡中基于網絡編碼的多路徑路由［J］.軟件學報，2010，21（8）：1908-1919.

［14］聶云峰，王長勝，陳崇毅，等.一種空間查詢高效的無線傳感網絡路由協議［J］.傳感技術學報，2015，（5）：744-751.

劉庭緒（1989-），男，安徽黃山人，碩士研究生，研究方向為無線傳感器網絡，zhaji2005@163.com；

李志華（1969-），男，湖南保靖人，博士，教授，碩士生導師，研究方向為網絡技術、信息安全、數據挖掘等，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

項目來源：中央科研專項基金項目（JUSRP211A41）；江蘇省科技廳產學研前瞻基金項目（BY2013015-23）

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