機會網絡中高效的數據分發機制
——CRLNC

喬晉龍，高 媛，劉亞翃，譚春花

（中北大學電子與計算機科學技術學院，山西太原 030051）

機會網絡中高效的數據分發機制
——CRLNC

喬晉龍，高 媛，劉亞翃，譚春花

（中北大學電子與計算機科學技術學院，山西太原 030051）

針對如何提高機會網絡中數據分發效率的問題，提出了一種數據分簇和隨機線性網絡編碼結合的數據分發機制——CRLNC。其核心思想是先將數據分成幾簇，然后在簇內分成相同數量的數據塊，源節點發送一簇中的數據塊，中間節點運用隨機線性編碼算法將其中的數據塊編碼轉發出去，目標節點接收到其中的編碼數據塊后采用高斯—約旦消元法將數據漸進還原。在這種數據分發機制中，針對節點緩存空間的冗余問題提出一種基于簇號和線性相關性的節點緩存策略。理論分析和仿真結果證明，與傳統的數據分發相比，該算法可以有效地提高網絡吞吐量，減小端到端的時延。

機會網絡;數據分發;隨機線性網絡編碼;線性相關性

【本文獻信息】喬晉龍，高媛，劉亞翃，等.機會網絡中高效的數據分發機制——CRLNC［J］.電視技術，2014，38（1）.

機會網絡是一種不需要源節點和目標節點間存在完整的通信鏈路，利用節點移動帶來的相遇機會實現通信的自組織網絡［1－2］。數據分發指源節點將數據通過某種機制轉發到目標節點的過程，是機會網絡研究的熱點之一。由于其節點移動劇烈、網絡鏈路頻繁斷裂等特點使基于存儲轉發的數據分發技術不能實現數據的理論傳輸容量，且具有高延遲、低數據率的特點，為了確保數據的可靠傳輸，研究一種適合機會網絡的數據分發機制很有意義。

網絡編碼［3］（Network Coding，NC）由R.Alshwede等首次提出，其原理為網絡中節點對接收到的多個數據塊進行編碼，編碼后的數據再由中間節點轉發，其最直接的應用就是數據分發。

針對上述問題，本文提出一種基于分簇的隨機線性網絡編碼（Clustering－Based Random Linear Network Coding，CRLNC）數據分發機制。目標節點在解碼時運用高斯—約旦消元法，使接收編碼數據塊和解碼同時進行來減小時延。數據塊在網絡中滯留的時間會很長，而節點緩存區有限，在數據量較大的情況下容易產生節點緩存區溢出的情況。因此，本文相繼提出一種基于簇號及線性相關性的節點緩存模型。當中間節點緩存區滿時，以“簇號”為索引優先存儲屬于同一簇的數據塊進行編碼。然后中間節點對同一簇的數據塊進行線性相關性檢測，決定數據塊的保留與丟棄。

1 研究現狀

通信網絡端到端的最大數據流，是由通信網絡中有向圖的最小割決定的［4］。傳統的機會網絡數據分發方式大多基于洪泛的傳染擴散方法，雖然可以適應網絡的拓撲動態性，卻幾乎不可能達到網絡數據流的上界。早期的數據分發策略主要依賴于數據發送者，例如有作者提出了一種Stored－GeoCast分發策略［5］，在該策略中發送者為準備發送的每個數據指定目標區域和有效期，在目標區域內的節點都可接收到數據。這種算法沒有注重數據的分類，同一條消息的副本過多，造成網絡負載增長過快從而使帶寬利用率較低。在后來提出的以內容為中心的數據分發方法LMDC中［6］，數據按內容種類進行分層，可以使用戶選擇自己感興趣的數據。該方法采用HEC，即源節點結合復制技術和EC處理后將數據發送出去。無論是哪種數據分發方式，中間節點對數據的操作只是存儲與轉發。

Katti等提出基于機會的網絡編碼方法（COPE）［7］，首次研究了網絡編碼在無線環境協議層面上的具體實現問題。COPE協議中每個節點對傳輸媒體進行偵聽，獲得它鄰居節點的狀態信息，決定編碼機會，并在本地的FIFO緩存結構內進行編碼，然后進行基于機會的路由。但是該協議需要節點存儲數據包并進行編碼，如果網絡出現擁塞，可能就會耗費較多的節點存儲空間。

碼構造算法是在數據分發系統中部署和實現網絡編碼的核心，R.Koeettr和M.Mdeard提出的代數法碼構造方式［8］，以及S.Jaggi等人提出的信息流法［9］，都要求在已知整個網絡拓撲信息的情況下，用一個系統轉移矩陣來描述源節點輸出的數據和目標節點接收到的數據的關系，通過構造符合要求的系統轉移矩陣來實現網絡編碼。機會網絡中的節點是隨機高速移動的，網絡的拓撲信息經常變化，這種方法代價很大。為使得網絡編碼在機會網絡中具有實際可用性，Li等人提出了線性網絡編碼的概念，證實節點進行線性網絡編碼運算，具有可行性，能夠達到最大流傳輸理論極限［10］。Ho等人提出了有限域下隨機線性網絡編碼的思想，并證實其有效性［11］。之后，隨機線性網絡編碼被應用于各個方面的研究，用于提高網絡吞吐量和能量利用率。

2 相關研究工作

2.1 CRLNC數據分發機制的數學模型

定義1（網絡模型）:圖G=（V，E）表示機會網絡，其中V表示所有節點的集合，源節點為S，目標節點的集合為R，任一目標節點表示為Ri∈R，E表示此刻所存在的所有鏈路的集合。

定義2（數據流向量）:源節點S發出的數據，鏈路e∈E上傳輸的數據，目標節點Ri∈R接收到的數據，均以向量的形式取之于有限域GF，該向量成為數據流（Data Flow）。假設源節點要發送的數據塊數目為n，則數據流向量為b=（b1，b2，…，bn），每個目標節點接收到的數據塊可用向量 r=（r1，r2，…，rn）表示。

定義3（系數矩陣）:中間節點接收到數據塊后對其進行線性組合時隨機在有限域GF內選取的數稱為隨機系數，表示為cij，i，j∈［1，n］。由隨機系數cij組合而成的矩陣為系數矩陣，表示為C。當目標節點接收到r時，若C滿秩（Full Rank），就能通過矩陣逆運算bT=C－1r解出源節點發送的數據流向量b。

定義4（轉移矩陣）:系數矩陣C稱為隨機線性網絡編碼相對于目標節點的轉移矩陣（Transfer Matrix）。

機會網絡CRLNC數據分發機制中各鏈路傳輸的數據、節點接收的數據和節點發出的數據均可表示為源節點發出數據流向量b中各元素的線性組合。因此，對于目標節點收到的任一數據塊ri∈r，有ri=ci1b1+ci2b2+…+cinbn，i∈［1，n］，矩陣形式為

2.2 CRLNC數據分發機制的算法實現

CRLNC數據分發機制的核心思想是利用機會網絡中節點的高運算能力，源節點將原始數據先分簇再分塊后將一簇內的數據塊順序發送出去。中間節點接收到數據塊后將其隨機線性編碼組合，目標節點收到滿足可解性條件的編碼數據塊后運用高斯—約旦消元法解碼獲得原始數據。目標節點具備可解性的條件是:目標節點接收到的線性編碼組合的編碼向量矩陣（即由編碼參數組成的矩陣）的秩大于或者等于所含數據塊的數量。

圖1表示了每個在機會網絡中傳輸的編碼數據塊結構，包含簇號CID、塊號ID、編碼向量和編碼信息。其中簇號CID表示該編碼塊屬于哪一簇，塊號ID是來標識該數據塊屬于某一簇的第幾塊，編碼向量的選取原則是從有限域GF（28）中隨機選取，編碼信息表示對原始數據或者已編碼數據進行線性組合的結果。

圖1 CRLNC數據分發機制的數據塊結構

如圖2所示，源節點S先將原始數據分成若干簇，再在每簇內分成大小相等的3個數據塊B1，B2，B3后，將其發送給目標節點R1和R2。下面描述機會網絡的中間節點如何運用隨機線性網絡編碼來完成到目標節點R1和R2的數據分發。其中，一簇數據塊傳輸完畢后再進行下一簇數據的線性組合、傳輸。編碼后的數據塊可表示為B'=∑ciBi。其中，ci為中間節點選擇的隨機系數，隨機系數的選取原則是從有限域GF（28）中隨機選取，Bi為原始數據塊。

圖2 CRLNC數據分發模型

源節點S將數據塊B1，B2，B3逐一發送出去，節點A，B，C，D，E是中間節點。其中節點A接收到數據塊B1，節點B接收到數據塊B2，節點C接收到B3。節點D接收到由節點A和B發送來的數據塊B1和B2后將其線性組合為c1B1+c2B2;節點E接收到由節點B和C發送來的數據塊B2和B3后將其線性組合為c3B1+c4B2，然后分別將編碼數據塊發送出去。目標節點R1只需接收到來自節點A的數據塊B1，來自節點D的編碼數據塊c1B1+c2B2或者來自節點E的編碼數據塊c3B2+c4B3的任意一個即可運用高斯—約旦消元法進行漸進式解碼來獲得原始數據塊B1，B2，B3。對于目標節點R2來說，同理可解碼出原始數據塊。

對于目標節點R1開說，若某時刻接收到3個線性無關的編碼數據塊B1，c1B1+c2B2和c3B2+c4B3，則可以得出三元方程組，即

目標節點接收到3個編碼數據塊后的編碼向量矩陣情況為

目標節點將編碼向量矩陣通過高斯—約旦消元法解碼原始數據塊B1，B2，B3。

高斯—約旦消元法屬于逐步解碼，也稱為漸進解碼。目的是為了減少解碼時間對端到端傳輸總體性能的影響，基本思想是使解碼和接收數據塊同時進行，從而節省時間。漸進解碼的具體方法是:每收到一個線性組合，使用初等行變換將由系數和線性組合而成的增廣矩陣化簡一次，使其變為行約簡階梯形矩陣，如

收到第3個線性組合并成功化簡后，增廣矩陣的左右兩側分別為3階單位矩陣和解碼出的原始數據分塊，如

式（5）所示增廣矩陣的右側即是通過高斯—約旦消元法解碼出的原始數據塊，結果為

下列偽碼描述了上述基于分簇的隨機線性網絡編碼數據分發機制的實現過程:

2.3 基于簇號及線性相關性的混合節點緩存機制

在CRLNC數據分發機制中，由于中間節點接收到的編碼數據塊可能是冗余數據，如果經常在節點間傳輸這種冗余數據，則會嚴重浪費帶寬和節點的計算資源，而且這種冗余數據會被其他中間節點重新進行隨機線性網絡編碼，在機會網絡中進行大范圍的傳播，導致整個網絡的數據分發效率極低。針對這個問題提出一種基于簇號及線性相關性的節點緩存機制，若接收到的編碼數據塊的編碼向量與節點已有的編碼數據塊向量線性相關，則節點直接丟棄接收到的編碼數據塊;否則，節點緩存該數據塊。機會網絡中節點執行該機制的偽代碼如下:

中間節點接收到編碼數據塊后，在該編碼塊和之前到達的編碼塊進行比較。如果傳送給中間節點的數據塊的簇號和該節點里其他編碼數據塊的簇號相同，那么檢測接收到的編碼數據塊對應的編碼向量是否已經存在于該節點，或者該編碼向量是否與該節點已經存在數據塊包含的編碼向量線性相關。若線性相關，則說明該數據塊是冗余數據，節點直接丟棄該編碼數據塊;否則，說明該編碼塊攜帶有新的數據，節點將緩存該編碼數據塊并再次進行線性編碼并轉發。總而言之，這種緩存機制能夠有效降低各中間節點執行編碼的計算消耗，同樣也緩解了機會網絡中的節點緩存矛盾。

3 仿真實驗與性能評價分析

實驗將在時延和網絡吞吐量性能方面分別對基于存儲和轉發的傳統的數據分發機制、一般的網絡編碼以及CRLNC機制進行性能評價，仿真軟件采用事件驅動的NS2仿真平臺，該軟件可以根據需要添加相關協議來確定節點的行為和節點之間數據傳輸的方式。

仿真場景為100 m×100 m的區域，隨機分布著1個源節點、2個目標節點和50個中間節點，原始數據長度L=10 Mbyte，在運用隨機線性網絡編碼時將原始數據分成10簇。

3.1 時延性能評價

在進行3種數據分發機制的時延性能分析時，根據每簇中的數據分塊數的變化來分析，將每一簇分別分為如圖3所示的數據塊數目。從圖中可以明顯看出，無論采用哪種數據分發機制，當每簇的分塊數為4時，即每個數據塊大小為256 kbyte時數據分發時延最小。因為若每簇的分塊數較小，則每塊的數據量較大，在發送過程中極可能由于數據丟失而重新傳輸;若每簇的分塊數較大，則每塊的數據量較小，這樣會增加數據發送的次數。這兩種情況都會導致高時延問題。在最開始發送數據量最大時，3種數據分發的時延都比較大，但是總體而言，網絡編碼機制要優于傳統的基于存儲和轉發的數據分發機制。本文提出的基于分簇的隨機線性網絡編碼數據分發機制在節點緩存問題上采用了不同的基于簇號及線性相關性的節點緩存策略，所以不會由于節點緩存滿，數據丟失后重傳而造成時延增大;目標節點在解碼時運用高斯—約旦消元法可以將接收數據和解碼數據并行執行，所以在很大程度上縮短了時延。

3.2 網絡吞吐量性能評價

圖3 數據分發機制時延性能評價

在進行3種數據分發機制的網絡吞吐量性能分析時，將每一簇分為4塊數據塊，即每塊大小為256 kbyte來進行仿真。如圖4所示的數據分發網絡吞吐量性能評價圖，從圖中可以看出，傳統的基于存儲和轉發的數據分發機制中，由于各鏈路上傳輸的數據不能被疊加，所以其吞吐量要遠遠低于兩種基于網絡編碼的數據分發機制，無法實現理論上的容量。而一般的網絡編碼對原始數據進行簡單的編碼操作然后發送出去，這種數據分發機制的吞吐量比傳統的數據分發機制要高很多，但是在數據量較大的情況下性能會降低。而基于分簇的隨機線性網絡編碼數據分發機制在數據量很大的情況下將原始數據分簇再分塊，減少了單次要傳輸的數據量，所以可實現高達9 Mbit/s的網絡吞吐量。

圖4 數據分發機制網絡吞吐量性能評價

由上述仿真結果分析可知，CRLNC在端到端延遲和網絡吞吐量性能指標上均表現良好，很好地解決了機會網絡中數據分發的問題。

4 小結

本文提出了一種機會網絡中基于分簇的隨機線性網絡編碼的數據分發機制，理論分析和仿真結果表明:與傳統的數據分發機制相比，CRLNC可以弱化甚至消除數據分發效率對原始數據大小的依賴，有效減少了單次要傳輸的數據量，提高了傳輸效率;基于簇號和線性相關性的節點緩存機制可以保證節點之間傳輸的編碼數據塊總是有效的，可以提高網絡帶寬利用率，節約節點的計算資源。總之，本文提出的數據分發模型能夠在一定程度上提高網絡編碼的執行效率，降低網絡編碼所需的計算消耗，進一步提升數據分發的性能。在今后的工作中，在擁有高效率網絡編碼的同時要進一步針對低復雜性的網絡編碼進行更深入的研究。

:

［1］熊永平，孫利民，牛建偉，等.機會網絡［J］.軟件學報，2009，20（1）:124－137.

［2］HU Q，ZHENG J.Weight pick:an efficient packet selection algorithm for network coding based multicast retransmission in mobile communication networks［J］.Wireless Networks，2013，19（3）:363－372.

［3］AHLSWEDE R，CAI N，LI S Y R，et al.Network information flow［J］.IEEE Transactions on Information Theory，2000，46（4）:1204－1216.

［4］ELIAS P，FEINSTEIN A，SHANNON C E.A note on the maximum flow through a network［J］.IEEE Transactions on Information Theory，1956，2（4）:117－119.

［5］MAIHOFER C，FRANZ W J，EBERHARDT R.Stored geocast［C］∥Proc.Kommunikation in Verteilten Systemen（KiVS）.［S.l.］:Springer Verlag，2003:257－268.

［6］CHEN L J，YU C H，TSENG C L，et al.A content－centric framework for effective data dissemination in opportunistic networks［J］.IEEE Journal on Selected Areas in Communications，2008，26（5）:761－772.

［7］KATTI S，HU W，RAHUL H，The importance of being opportunistic:practical network coding for wireless enviroments［EB/OL］.［2013－01－01］.https://www.cl.cam.ac.uk/research/srg/netos/papers/2005－allerton－netcoding.pdf.

［8］HO T，LUN D S.Network coding:AN Introduction［D］.Cambridge:Cambridge University，2008.

［9］JAGGI S，LANGBERG M，KATTI S，et al.Resilient network coding in the presence of byzantine adversaries［J］.IEEE Transactions on Information Theory，2008，54（6）:2596－2603.

［10］LI S Y R，HO S T.Ring－theoretic foundation of convolutional network coding［C］//Proc.Fourth Workshop on Network Coding，Theory and Applications.Hong Kong:IEEE Press，2008:1－6.

［11］HO T，KOETTER R，MEDARD，M，et al.A random linear network coding approach to multicast.IEEE Trans.Inform.Theory，2006，52（10）:4413－4430.

［12］黃辰，王芙蓉，戴彬，等.基于網絡編碼的無線自組織網數據分發機制［J］.電子學報，2010（8）:1852－1857.

CRLNC:Efficient Data Dissemination Mechanism For Opportunistic Network

QIAO Jinlong，GAO Yuan，LIU Yahong，TAN Chunhua

（Colleage of Computer Science and Technology，North University of China，Taiyuan 030051，China）

Aiming at improving the efficiency of data dissemination in opportunistic network，an efficient data dissemination mechanism combined with clustering and random linear network coding is proposed.The core idea is dividing the data into several clusters firstly，and then dividing each cluster into the same number of data blocks，the source node sends the data blocks in each cluster，the intermediate node encodes the data blocks with random linear coding algorithm and then forwards the encoded data block，the destination node uses Gauss－Jordan elimination method to restore the data progressively after receiving the encoded data blocks.Aiming at the redundancy of node cache space，this data dissemination mechanism proposes a node caching strategy based on cluster number and linear correlation.Theoretical analysis and simulation results show that CRLNC outperforms the traditional data dissemination mechanism，CRLNC mechanism effectively improves network throughput and reduces the end－to－end delay.

opportunistic network;data dissemination;random liner network coding;linear relevance

TN915;TP393

B

責任編輯:許 盈

2013－03－12