Ａｄ Ｈｏｃ網絡中基于熵的ＱｏＳ多播路由研究

摘要：Ad Hoc網絡自身固有的特點使得Ad Hoc網絡的QoS路由協議面臨許多新的挑戰和機遇，而且出現了許多新的網絡系統，如視頻點播、遠程教學、遠程醫療等，這些多媒體實時系統已經不滿足網絡的單播數據。因此，網絡數據的多播提上了日程。本文對QoS多播路由進行了闡述，提出了一種基于熵的穩定的QoS多播路由，并且對它進行了分析以及與已經存在的多QoS約束多播路由進行了比較。

關鍵詞：Ad Hoc網絡；多播路由；QoS多播路由；基于熵的QoS多播路由

中圖分類號：TP393文獻標識碼：A文章編號：1009-3044(2008)34-1634-03

A QoS Multicast Routing A Study of Ad Hoc Networks Based on Entropy

XU Jian-e1， WANG Xin-hua1， ZHU Yan-sheng2

(1.Information Science and Engineering College， Shandong Normal University，Ji'nan 250014，China; 2.Middle School of Shandong Dezhou Wang Cun Dian， Dezhou 253036， China)

Abstract: QoS routing protocols of Ad Hoc networks face lots of new challenges and opportunities because of the inherent characteristics of Ad Hoc networks， and lots of new network systems are applied， for example，video on demand，remote instruction、remote medication，etc. These Medium real time systems do not already satisfy the network unicast data.So， network data multicast has mentioned an agenda. The paper describes the QoS multicast routing， presents a stable QoS multicast routing based on entropy， and carries out analysis on it as well as compares it with many existent QoS restrain multicast routing.

Key words: ad hoc network; multicast routing; QoS multicast routing; QoS multicast routing based on entropy

1 引言

Ad Hoc網絡又稱移動Ad Hoc網絡（mobile Ad Hoc networks ，MANET）是一種沒有基礎設施支持的移動網絡，具有無中心、帶寬有限、自組織、動態的網絡拓撲結構及安全性差等特點[1] ，傳統的路由不能滿足Ad Hoc網絡的需要。 而且隨著用戶要求的提高，要求Ad Hoc網絡支持更高的服務質量，所謂服務質量（QoS：Quality-of-Service）是指網絡在傳輸數據流時要求滿足一組服務請求，強調端到端的（End-to-End）或網絡邊界的整體性，具體可以量化為帶寬、延遲、延遲抖動、丟失率、吞吐量等性能指標[2]。

隨著網絡通訊技術的快速發展，許多新的網絡應用系統已經出現，如視頻點播、遠程教學、遠程醫療及網上拍賣等，而這些多媒體實時系統對網絡的服務質量要求更高，單播通信已經不能滿足用戶的需要了，多播通信應運而生。由于多播對帶寬、延遲等服務質量要求更高，占用的資源也多，加重了網絡傳輸的負載。因此，為了優化多播，多播通信通常是建立樹狀路由，數據只能在樹的分叉處復制，能夠節省帶寬，降低服務器負載，降低網絡負載和減少擁塞，從而提高了網絡的壽命[3]。

2 多播路由選擇的QoS參數

區別于單播通信（在發送者和每一個接收者之間需要單獨的數據信道），多播通信（從一個發送者同時向特定的多個接收者傳送數據的通信過程）的關鍵是多播路由的選擇，也就是如何構建一棵多播分布樹，用以在轉發數組時能保證用戶服務質量的要求。因此，找出既能滿足應用服務質量需求，又具有最小代價的多播路由對保證多播應用系統的正常高效運行具有很重要的意義。

目前，支持QoS的多播路由算法有很多，如基于源路由策略構造Steiner樹，包括KPP、BSMA、CSPT等；采用遺傳算法求解最小延遲的多播路由算法[4]；結合QoS的多個約束條件和遺傳算法構造多播樹；基于多個QoS約束的多播樹[5]；基于分層結構的QoS多播路由[6]；基于粒子群的QoS多播路由[7]。在以上種種算法中，基于源路由策略構造Steiner樹是最為常用的算法。

所有構造多播樹的路由算法都是以QoS的參數作為基本約束條件的，路由選擇的結果是產生一棵滿足帶寬、剩余能量、延遲、延遲抖動等約束條件的多播樹。幾乎所有的多播樹算法都是形成以最小延遲為代價的多播樹，在不違反時延約束的同時，運用平衡代價與時延函數求解最小值，最后用受限最低代價路徑代替最小生成樹中的相應的邊并消除可能存在的環路，最終得到一棵時延受限最低代價多播樹[8]。

假設+R表示正實數集，R+表示負實數集。用有向圖G=(V，E)表示網絡結構，V代表網絡節點，E代表雙向通信鏈路網絡鏈路集。對于任一條鏈路e，具有e∈E。

定義1 對于任一條鏈路e∈E，我們可以定義4個QoS參數函數；延遲函數delay(e):E→+R；帶寬函數bandwidth(e):E→+R；費用代價函數cost(e):E→+R；延時抖動函數delay-jitter(e):E→+R；

定義2 對于任一個節點ν∈V，我們可以定義4個QoS參數函數：節點延遲函數delay(v):V→+R；節點費用代價函數cost(v):V→+R；節點延時抖動函數delay-jitter(v):V→R+；節點分組丟失率函數packet-lost(v):V→R+。

設S∈V是多播樹T的源節點，D?哿V-{s}為多播樹T的目的節點集，T(s，D)為源節點s和目的節點集D組成的多播樹T。t為多播樹從源節點s到目的節點集D上的一點，t∈D，設PT(s，t)為從源節點s到t的路由路徑，則對于s和D存在如下關系：

延遲：■

帶寬： Bandwidth(PT(s，t))=min{bandwidth(e)，e∈PT(s，t)}

抖 動：■

丟失率：■

費用代價：■

至此，我們分析了源節點S和目的節點集D之間的QoS參數值的變化情況。基于此內容，我們得到了QoS多播路由問題的定義：

定義3QoS多播路由問題：給定網絡結構G=(V，E)，多播源節點s∈V，多播目的節點集D?哿V-{s}，延遲函數delay(*):E∈+R；帶寬函數bandwidth(*):E∈+R；費用代價函數cost(*):E∈+R；延時抖動函數delay-jitter(*):E∈+R；節點分組丟失率函數packet-jitter(*):E∈+R，尋找一棵多播樹必須滿足：

①延遲：Delay(PT(s，t))≤Dmax ;

②帶寬：bandwidth(PT(s，t))≤Bmin ;

③抖動：packet-jitter(PT(s，t))≤Jmax；

④丟失率：packet-lost(PT(s，t))≤Lmin；

⑤費用代價約束：在所有滿足①~④條件的多播樹中，選擇一棵cost(PT(s，t))最小的樹，若同時存在多棵這樣的多播樹，可以將其他的多播樹作為備用的選擇。

其中，t∈D，PT(s，t)為T(s，D)上源節點s到目的節點集D的路由路徑，Dmax，Bmin，Tmax，Lmin分別為由用戶或應用提供的極限延遲、帶寬、抖動和丟失率的請求值。

3 基于熵的QoS多播樹

3.1 信息熵

在此引入一個新的概念——熵，1948年，香農提出了“信息熵”，信息熵是信息論中用于度量信息量的一個概念，解決了對信息的量化度量問題。

定義 設試驗α只有有限個互不相容的結果：A1，…An各自對應的概率為P(A1)，，P(A2)，…，P(An)則定義α的信息熵為

■，以10為底對數熵的單位常用哈特萊(Hartley)表示。這只是一個計量單位，也可以2為底對數熵的單位為比特(bit)。這個定義可以理解為：-lgP(Ai)使試驗α的結果Ai的不確定程度；將各個結果的不確定性加權平均值作為試驗α的總的不確定性的度量，這就是試驗的信息熵H(α)，或者記為H(P1，P2，，…Pn)，簡稱熵。熵值越大，不確定程度就越大，變量的不確定程度越大，把它搞清楚所需要的信息量也就越大；反之亦然。一個系統越是有序，信息熵就越低。反之，一個系統越是混亂，信息熵就越高。所以，信息熵也可以說是系統有序化程度的一個度量。

熵在研究領域有著廣泛的應用，如王琰在基于熵的柱面全景圖拼接算法及其魯棒性分析，利用局部熵的定義改進了算法，極大的提高了穩定性；劉明在基于熵理論的船舶電力系統脆性分析，通過對船舶電力系統脆性概率熵來分析船舶電力系統的脆性；陳建華在基于熵理論的企業組織創新分析，改進了導入管理負熵和建立耗散結構的措施等。在路由方面的應用，沈暉在基于熵的分布式QoS路由（EBLLD）提出了衡量路徑穩定性的新尺度——熵，并利用熵在源節點和目的節點之間選擇比較穩定的路徑，減少了重建（或修復）路由的次數，從而使得所構建的多播樹比較穩定，為拓撲結構變化頻繁的Ad Hoc網絡環境盡可能提供QoS保證。

3.2 信息熵的改進

論文中引用的熵都是對信息熵進行了改進，并不是嚴格意義上的熵。假設熵是一種用來衡量路徑穩定性或路徑壽命的尺度，對于從節點i到節點j的路徑P，其中節點i的特征變量：

■（1）

其中s，pos(s)，d，pos(d)， v(s)，v(d)，R分別是源節點，源節點的位置向量，目的節點，目的節點的位置向量，源節點的速度向量，目的節點的速度向量和兩點之間的傳輸半徑（假設節點間的傳輸半徑相同）。Post(i，j，t)=post(i，t)- post(j，t)表示在t時刻節點i和節點j之間的相對位置向量，v(i，j，t)= v(i，t)- v(j，t)表示在t時刻節點i和節點j之間的相對速度向量，N是在時間間隔Δt內離散時刻的個數（每隔一個時間間隔Δt，相對位置向量和相對速度向量就被計算和更新）。

其中，節點i處： ■（2）

F(i)表示節點i的鄰居節點集或者子集，C(F(i))表示集合F(i)的度，在這里■，（3）

路徑P(i，j)越穩定，則Hp(i，j)就越大，因此，我們得到了表征路徑穩定性的加性尺度——熵：■，（4）

這里Nr表示節點i到節點j的路徑P上的節點數，Δt表示一個時間間隔。

3.3 基于熵的QoS多播路由選擇算法

對于多播樹的構建都是在理想的情況下，假設節點不移動或者移動的速度和距離相對較小的情況，而Ad Hoc網絡本身所固有的動態拓撲結構使得 剛剛構建好的多播樹由于某個節點或者某些節點的加入或者離開，導致了多次重構多播樹，浪費了大量本來就不充足的網絡資源，這種不穩定的現象容易引起如視頻點播等實時系統用戶的不滿意。因此，需要構建一種基于多QoS約束條件下的穩定的、可靠的多播樹，來適應Ad Hoc網絡的動態拓撲結構。基于熵的QoS約束多播樹結合了多QoS路由算法和熵的優點，比較適合Ad Hoc網絡。此外，該算法能以較小的路由開銷獲得較高的路由成功率，具有很好的可擴展性，可以應用于較大規模的Ad Hoc網絡中。

假設源節點為s發出連接請求，每個連接請求包括如下信息：s，pos(s)，d，pos(d)，v(s)，v(d)，R（這些數據可以通過GPS獲得），目的節點為 （d∈D）。其中i，j為從s到d的路徑上某些中間節點，其中d(s，*)和dj(s，*)分別表示從s到d該路徑某個中間節點的延遲之和及延遲抖動之和，bw(i，j)是路徑p(s，d)上兩個節點i和j之間的帶寬。

基于熵的QoS多播路由算法具體如下：（如下圖）

■

初始H(s)=0，設s的鄰居節點集為Ωs，i∈Ωs，

步驟1 ■

則利用公式（1）（2）（3）（4）計算H(s，i)，H(s)= H(s)+ H(s，i)，轉步驟2否則轉入步驟3

步驟2 尋找i的鄰居節點集Ωi，j∈Ωi，若■

則計算H(I，j)，H(s)= H(s)+ H(i，j)；若j∈D則d1=j，H(s，d1)=H(s)，轉入步驟4；否則i=j，轉入步驟2；

步驟3 尋找Ωs中的另一個節點i轉入步驟1；

步驟4 將p(s，d1)路徑上的各點加入多播樹T(s，D)，轉步驟5；

步驟5 比較H(s，d)，選擇一條H(s，d)值最大的路徑作為最佳路徑，如果存在多條熵值相同的路徑，則選擇跳數最少的路徑，其它的作為備用路徑；

步驟6目的節點沿此路徑的逆向路徑向源節點 發送路徑證實消息，并且沿途預留資源。當路由證實消息到達源節點時，該連接已經成功的建立了路由，源節點可以開始數據傳輸了。

4 性能分析

基于熵的QoS多播路由是對基于QoS約束條件的多播路由的優化，因此，基于熵的QoS多播路由比單純的基于QoS約束條件的多播路由更加穩定和可靠，而且還避免了環路問題，在路徑選擇過程中是基于最小延遲和最小熵的折中來選擇的。與一般的多QoS約束的多播路由的性能比較如下：

■

5 結束語

該文提出了一種基于熵的多QoS約束的多播路由選擇方法，是QoS約束的多播路由選擇的優化，結合已經存在的多播路由的優點，在此基礎上增加了一個更加穩定的性能，使得所構建的多播樹更加穩定、可靠，避免了環路，減少了由于節點的頻繁移動而造成的網絡中斷，避免了資源的浪費，更適合Ad Hoc網絡的高度動態的環境。而且結合了分布式路由算法，可以獲得全局最優解，使得其具有很強的可擴展性，可以適用于較大規模的Ad Hoc網絡中以滿足各種多媒體網絡服務質量和實時性的需要。在熵的研究領域還存在許多復雜的問題，如何將熵這個概念更好的應用到Ad Hoc網絡中，是下一步主要研究的課題。

參考文獻：

[1] 肖小玲，李臘元，張翔，等.基于Ad Hoc網絡的QoS路由協議研究[J].計算機應用研究，2006(9):216-219.

[2] Sivakumar R，Sinha P， Bharghavan V.CEDAR A Core-extraction DistributedAd

hoc Routing Algorithm[J].IEEE Journalof Selected Areas in Communications Special Issue on Ad hoc Networks，1999，17(8):1454-1465.

[3] 楊德紅，瞿中，何江平，等.QoS多播路由算法研究[J].計算機工程與設計，2005，10(26):2730-2733.

[4] 陳年生，柯宗武，等.Ad Hoc網絡中基于分層結構的QoS多播路由算法[J].計算機工程與應用，2006(18):123-126.

[5] Toh C K. Assiciatibity_bassed routing for ad hoc mobile networks[J].Wirless Personal Communinations，1997，4(2):103-109.

[6] 向陽，李臘元，等.基于Ad Hoc的QoS多播路由協議研究[J].計算機工程與應用，2006(10):147-150.

[7] 沈暉，石冰心，鄒玲，等.Ad Hoc網絡中基于熵的長壽分布式QoS路由算法[J].軟件學報，2005，16(3):445-452.

[8] Lin C R，Liu J S.QOS routing in Ad hoc wirless networks[J].IEEE Journal on Selected Areas in Communications，1999，17(8):1426-1438.

[9] Mauve M，Widmer A，Hartenstein H.A surveyon position-based routing in mobile Ad Hoc networks[J].IEEE Network，2001，15(6):30-39.