基于二次置換多項式的滑動窗口網(wǎng)絡編碼算法

桂 超，夏承林，孫寶林，宋 鶯

(1.湖北經(jīng)濟學院信息與通信工程學院，武漢 430205;2.湖北大學計算機與信息工程學院，武漢 430062)

無線網(wǎng)絡的能量、鏈路帶寬、計算和存儲能力等都受到一定的限制，提高無線網(wǎng)絡的鏈路帶寬、網(wǎng)絡吞吐量是無線網(wǎng)絡一直探索解決的問題.網(wǎng)絡編碼最早是由Ahlswede等學者提出的一種基于有限域GF(2q)上的代數(shù)運算，可以最大限度地提升無線網(wǎng)絡的帶寬、數(shù)據(jù)傳輸可靠性、網(wǎng)絡吞吐量等，較好地降低數(shù)據(jù)分組編碼的計算復雜性和解碼過程[1-6].

在無線網(wǎng)絡中，相關文獻研究表明網(wǎng)絡編碼在有限域上的性能比二進制編碼域上具有更好的穩(wěn)定性.牛騰等學者針對基于Device-to-Device的無線多媒體網(wǎng)絡編碼廣播重傳策略，提出了一種最大權(quán)重網(wǎng)絡編碼選擇算法(MWSA-NC)，MWSA-NC算法能極大地提高系統(tǒng)吞吐量，降低解碼時延和減少視頻流失真[7].Fiandrotti等學者基于無線網(wǎng)絡中提出了一種帶碼網(wǎng)絡編碼算法，該算法的目的是在數(shù)據(jù)分組編碼、分組重組和解碼分組機制中保持良好的數(shù)據(jù)分組信息[8].Seferoglu等學者以感知隊列技術為基礎，在編碼過程中，以感知隊列管理形式構(gòu)建算法(NCAQM)，該算法在中間節(jié)點上實現(xiàn)數(shù)據(jù)分組的網(wǎng)絡編碼[9].Lucian等學者分別研究了不同的線性置換多項式(LPPs)、QPPs、CPPs等之間的數(shù)量關系及特性.分析了基于二次多項式系數(shù)和三次多項式系數(shù)的QPPs和CPPs的充要條件和中國剩余定理.構(gòu)建了一種新的基于線性置換多項式的編碼/解碼算法，可以更好地降低數(shù)據(jù)傳輸?shù)牟铄e率和降低網(wǎng)絡編碼的計算復雜性[10].Hong等學者針對網(wǎng)絡中的滑動窗口機制問題進行了研究，提出了一種帶滑動窗口解碼(SNNC-SW)的短消息噪聲網(wǎng)絡編碼，該算法的網(wǎng)絡編碼解碼復雜性低、解碼時延低、擴展速度較快[11].Lee等學者提出了一種生成網(wǎng)絡編碼數(shù)據(jù)分組的協(xié)議，它利用多播路由信息和視頻數(shù)據(jù)分組流信息對數(shù)據(jù)分組流進行網(wǎng)絡編碼，該協(xié)議通過隨機線性網(wǎng)絡編碼算法對數(shù)據(jù)分組進行批量解碼，較好地提升了數(shù)據(jù)的傳輸效率、降低了數(shù)據(jù)分組的差錯率和解碼時延[12].

考慮到無線網(wǎng)絡中節(jié)點的移動性強和網(wǎng)絡拓撲的快速變化，田賢忠等學者提出了一種基于網(wǎng)絡編碼的優(yōu)化策略，該策略讓瓶頸區(qū)域的部分節(jié)點進行網(wǎng)絡編碼，然后再轉(zhuǎn)發(fā)給匯聚節(jié)點，較好地減少了數(shù)據(jù)分組的轉(zhuǎn)發(fā)次數(shù)和降低了能量消耗[13].Kiss等學者針對無線網(wǎng)絡的數(shù)據(jù)傳輸可靠性和協(xié)作編碼機制，提出了一種無線傳感器網(wǎng)絡的數(shù)據(jù)協(xié)作傳輸可伸縮的算法，該算法是一種基于Reed-Solomon編碼為基礎的網(wǎng)絡編碼協(xié)作算法，較好地提升了數(shù)據(jù)傳輸?shù)目煽啃訹14].Ostovari等學者針對編碼/解碼的時間復雜性，采用隨機線性編碼技術，基于輔助節(jié)點提出了一種代替層間網(wǎng)絡編碼的一般形式，能夠較好地降低了節(jié)點的編碼時間和解碼時間[15].Junior等學者針對無線傳感器網(wǎng)絡中的能源效率、數(shù)據(jù)傳輸可靠性等問題，提出了一個基于數(shù)據(jù)分布的最小能源消耗的網(wǎng)絡編碼算法(CodeDrip)，CodeDrip算法可以較好地提高節(jié)點的能源效率、數(shù)據(jù)傳輸?shù)目煽啃院蛿?shù)據(jù)吞吐量，可以應用于無線傳感器網(wǎng)絡中提升網(wǎng)絡的性能.考慮到無線網(wǎng)絡中不同接收節(jié)點間的計算能力、解碼能力等相關復雜性問題[16]，Qu等[17]學者提出了一種分類網(wǎng)絡編碼的編碼參數(shù)選擇算法.

Nieminen等學者提出了一種基于蝶形網(wǎng)絡的二次置換多項式(QPP)，作為譯碼器單元與存儲器之間的互連網(wǎng)絡，支持多種靈活、無沖突的并行代碼訪問方法.主要優(yōu)點是為高速輪機譯碼器提供了大量新的并行架構(gòu)，支持集上的二次置換多項式[18].王冠等學者提出的不規(guī)則Block-LDPC代碼方案可以提供更好的誤碼性能和降低復雜度[19].Trifina等[19]學者將二次置換多項式編碼器和幾乎正則置換多項式(ARP)編碼器的等價條件擴展為三次置換多項式(CPP)編碼器.實驗結(jié)果表明，CPP編碼器的性能贊同于始終等同于(ARP)，但編碼長度小于一個的ARP編碼器.

針對無線網(wǎng)絡的分組傳輸機制、數(shù)據(jù)吞吐量和編碼的解碼延遲等相關問題.本文將二次置換多項式、滑動窗口機制應用于網(wǎng)絡編碼方法中，構(gòu)造了一種無線網(wǎng)絡中基于二次置換多項式的滑動窗口網(wǎng)絡編碼算法(QPPSW-NC)，為無線網(wǎng)絡的編碼效率、解碼復雜度、能源效率等性能的改善提供理論支持和性能評價.

1 二次置換多項式的滑動窗口機制

本節(jié)基于二次置換多項式、滑動窗口和隨機線性網(wǎng)絡編碼技術，探討在同一窗口中的數(shù)據(jù)分組進行編碼/解碼的有關操作基本原理和機制.

1.1 二次置換多項式(QPP)

一個二次置換多項式p(x)可以定義為：p(x)=ax2+bx，其中a、b、x都是非負整數(shù)，即對于任意x∈ZN，p(x) 的模是N.因此，整數(shù)a，b，N之間需要滿足一定的條件，方可讓p(x)是ZN上的置換多項式.相反地，若p(x)是ZN上的置換多項式，那么整數(shù)a，b，N之間需要滿足一定條件.按阿基米德定理，正整數(shù)均可能夠分解為若干素數(shù)帶一定冪次方的乘積，正整數(shù)的素數(shù)因式分解中每個素數(shù)的值總是大于或等于1.只有有限數(shù)量的素數(shù)才能進入到正整數(shù)的素數(shù)形式乘積分解.以下用gcd(x，y)代表正整數(shù)x和y的最大公約數(shù).

定理1二次多項式p(x)=ax2+bx(modN)作為置換多項式的充要條件可分為兩種情況：

1)對所有的N≥2，gcd(b，N)=1，N的每個素數(shù)因子都是a的因子；

2)對所有的a和b(a≥1，b≥1)，a+b是奇數(shù)、gcd(b，N/2)=1，N的不等于2的每個素數(shù)因子都是a的因子.

定理2如果p(x)是二次置換多項式，則p(x)可以生成一個無窮序列：

p(x)=2k+1x2+(2k-1)x，k=1，2，3，….

(1)

嚴格地說，只有當k>3時，才有二次置換多項式編碼器的存在.第一個觀察結(jié)果是k=1和k=2時對應的.

定理3二次置換多項式p(x)=ax2+bx(modN)在整數(shù)集ZN上是不可約的，當且僅當N>gcd(N，2a).

設p(x)=84x2+41x模112，即N=112=2471和84=223171.如此N=112的素數(shù)因子都是a=84的因子，且gcd(41，112)=1，這里p是一個二次置換多項式和校驗gcd(112，168)=56，得到p是不可約的.通過觀察N=112的因子，可以得出二次置換多項式p支持4個窗口大小，分別為56、28、14和7，用于同時訪問2、4、8和16個外部值.

圖1展示了當N=112時，子窗口的長度為14時的外部值計算方法.每個單元格中的數(shù)字表示外部值ei的索引(i=0，1，2，…，111).

圖1 子窗口的長度為14和外部值N=112Fig.1 The length of the child window is 14 and the external value N=112

1.2 滑動編碼窗口

傳統(tǒng)的滑動窗算法的窗長是固定的，算法的復雜度與滑動窗的長度成正比.將滑動窗口和隨機網(wǎng)絡編碼方法進行融合，可以適當降低參加滑動窗口中進行編碼/解碼的數(shù)據(jù)分組數(shù)量，減少網(wǎng)絡時延和能量消耗.

為進一步提高無線網(wǎng)絡的服務質(zhì)量和效率，結(jié)合滑動窗口的特點，本文提出了一種二次置換多項式(QPP)確定長度的滑動窗口算法.QPP滑動窗口長度算法的一般結(jié)構(gòu)和過程與傳統(tǒng)的滑動窗算法類似，但是滑動窗口的大小是根據(jù)滑動過程中的二次置換多項式進行調(diào)整的.算法的QPP滑動窗口長度可以自適應地調(diào)整每個滑動窗口的長度，避免滑動窗口的長度過大或過小.

圖2顯示了為QPP長度滑動而提出滑動機制的結(jié)構(gòu).假設數(shù)據(jù)的長度為N個信息位，滑動窗口的長度為w信息位和w的整數(shù)倍數(shù).讓我們定義第i(1≤i≤N/w)向前遞歸和第i個向后遞歸計算的度量，向后遞歸計算從第(i-1)次滑動窗口開始的位置到第i個滑動窗口開始的位置.

圖2 QPP滑動窗口機制Fig.2 QPP sliding window mechanism

1.3 滑動窗口的概率分配

一旦設置了滑動窗口的邊界區(qū)域，就可以對滑動窗口中數(shù)據(jù)分組數(shù)量、編碼/解碼過程進行數(shù)學上的描述研究.

滑動窗口w內(nèi)數(shù)據(jù)分組d在位置q的相關概率用P(dq，w|s)表示，則在此機制下輸入系統(tǒng)s的概率可表示為：

(2)

在此概率下，滑動窗口可以較好地使得窗口平滑移動.

2 QPP-SWNC編碼機制與解碼復雜度的分析

2.1 編碼/解碼規(guī)則

數(shù)學上，無線網(wǎng)絡結(jié)構(gòu)可用無向圖G=(V，E)表示，集合V代表移動節(jié)點的集合，集合E代表無線網(wǎng)絡鏈路邊集.鏈路可用e=(i，j)∈E代表節(jié)點i與節(jié)點j之間有邊相連，如果(i，j)∈E且(j，i)∈E，假設無線鏈路是對稱的，兩個無線鏈路是否相互干擾取決于所采用的干擾模型.

網(wǎng)絡編碼過程是在有限域GF(2q)中隨機選取的源向量系數(shù)的線性組合.讓x0，x1，…，xn-1表示與該移動節(jié)點相關聯(lián)的源數(shù)據(jù)分組.線性網(wǎng)絡編碼允許從中間移動節(jié)點輸入組合數(shù)據(jù)分組.每個組合數(shù)據(jù)分組包含一個源數(shù)據(jù)分組的線性組合，它被描述為編碼向量的源數(shù)據(jù)分組的因子向量，也被附加到數(shù)據(jù)分組上.

無線網(wǎng)絡移動節(jié)點利用編碼向量對數(shù)據(jù)分組進行編碼和解碼操作.該算法可以遞歸地執(zhí)行編碼操作并獲得已編碼后的數(shù)據(jù)分組.

2.2 QPP-SWNC解碼復雜度的分析

假設移動源節(jié)點對于發(fā)送的數(shù)據(jù)分組有一個大小為W的滑動窗口.設ti表示分組i在滑動窗口中的時間，Di(ti)表示分組i的滑動窗口ti秒時間內(nèi)解碼數(shù)據(jù)分組的數(shù)量.則最大化目標可以表示為最大化DW的總數(shù)量：

(3)

其中，M為數(shù)據(jù)分組大小，W為以數(shù)據(jù)分組計算的滑動窗口大小，T是在滑動窗口內(nèi)對數(shù)據(jù)分組進行編碼和解碼的處理時間.

將具有同樣數(shù)量的滑動窗口內(nèi)的待編/解碼處理的數(shù)據(jù)分組歸并為一個序列，nk代表第k組的數(shù)據(jù)分組個數(shù)，則最多有效可處理總量如下：

(4)

這里將滑動窗口的解碼效率定義為

(5)

從而可以定義分組i的解碼效率為

(6)

根據(jù)公式(4)～(7)，其最大化目標可以改寫為：

(7)

其中，ak表示k組滑動窗口：

(8)

在QPP-SWNC算法中，對任意時刻t，初始化滑動窗口需要O(N)時間，找到滑動編碼窗口需要O(e)時間，從而構(gòu)造一個滑動窗口需要O(eTN)時間，可以得到QPP-SWNC算法在一個滑動窗口中的解碼需要O(T2N)時間.

3 仿真實驗

在本節(jié)中將對QPPSW-NC算法進行性能評價和比較仿真研究，在仿真實驗中，將QPPSW-NC算法與SNNC-SW算法[10]和CodeDrip算法[15]進行對比分析.在仿真實驗中，將采用網(wǎng)絡仿真軟件NS2[20]進行仿真實驗研究.

3.1 實驗環(huán)境

在這一節(jié)中給出了一種無線網(wǎng)絡中基于二次置換多項式滑動窗口的網(wǎng)絡編碼算法(QPPSW-NC)的仿真實驗.移動節(jié)點是隨機和均勻坐落在1000×1000 m2的區(qū)域內(nèi)，移動節(jié)點的傳輸半徑為250米，在此區(qū)域內(nèi)，源節(jié)點自由選擇并發(fā)送數(shù)據(jù)分組，其他節(jié)點接收數(shù)據(jù)分組.各移動節(jié)點自主隨機移動，編碼數(shù)據(jù)分組的丟失率分布相同，均值為0.01%且彼此獨立.表1為仿真實驗參數(shù).

表1 仿真實驗參數(shù)Tab.1 Simulation experiment parameters

3.2 實驗結(jié)果

首先仿真分析QPPSW-NC在網(wǎng)絡移動節(jié)點移動速度變化情況下的網(wǎng)絡吞吐量的性能.將網(wǎng)絡吞吐量與移動節(jié)點的移動速度變化情況下進行比較分析，其QPPSW-NC、SNNC-SW和CodeDrip三種算法的仿真結(jié)果如圖3所示.從圖3中可以看出，當節(jié)點的移動速度從慢到快增加時，QPPSW-NC算法的平均網(wǎng)絡吞吐量要高于SNNC-SW和CodeDrip算法.因此，使用二次置換多項式滑動窗算法可以更好地提高滑動窗數(shù)據(jù)編碼的效率.

圖3 在節(jié)點移動速度變化下網(wǎng)絡吞吐量的比較Fig.3 Comparison of network throughput under the change of node movement speed

然后測試和分析QPPSW-NC算法中編碼開銷與節(jié)點移動速度的性能.將編碼開銷與移動節(jié)點移動速度變化情況下進行了性能分析，其QPPSW-NC、SNNC-SW和CodeDrip三種算法的仿真結(jié)果如圖4所示.編碼開銷隨著移動節(jié)點移動速度的增加而增加，即當節(jié)點的移動速度增加時，編碼成本也相應增加.從圖4中可以看出，QPPSW-NC算法的編碼開銷在節(jié)點的移動速度增加時，也表現(xiàn)出編碼開銷最低的性能.

圖4 在節(jié)點移動速度變化下編碼開銷的比較Fig.4 Comparison of coding overhead under the change of node movement speed

圖5中比較了QPPSW-NC算法與SNNC-SW算法和CodeDrip算法在移動節(jié)點移動速度變化下的平均解碼延遲.從圖5中可以看出，QPPSW-NC算法的解碼延遲最小，因為QPPSW-NC算法采用了QPP長度滑動窗口機制，QPP長度滑動窗口中可以提供最優(yōu)數(shù)量的編碼/解碼數(shù)據(jù)分組，從而使得解碼數(shù)據(jù)分組的時延最低.

圖5 在節(jié)點移動速度變化下解碼延遲的比較Fig.5 Comparison of decoding delay under the change of node movement speed

隨著移動節(jié)點移動速度的增加，移動節(jié)點之間的距離不斷變化，移動節(jié)點的能耗也隨之增加.圖6中比較了QPPSW-NC算法與SNNC-SW算法和CodeDrip算法在移動節(jié)點移動速度變化下的網(wǎng)絡能源消耗情況.從圖6可以看出，QPPSW-NC的能耗消耗低于SNNC-SW算法和CodeDrip算法.這說明QPPSW-NC比其他算法具有更低的能耗.

圖6 在節(jié)點移動速度變化下網(wǎng)絡能源消耗的比較Fig.6 Comparison of network energy consumption under the change of node movement speed

圖7展示了移動節(jié)點在不同移動速度下能源效率與移動節(jié)點移動速度的比較關系.當移動節(jié)點的移動速度變大時，移動節(jié)點的能源消耗也開始增加從而其能源效率也開始下降.從圖7可以看出，QPPSW-NC的能源效率高于SNNC-SW算法和CodeDrip算法的能源效率.這說明QPPSW-NC比其他算法具有更高的能源效率.

圖7 在節(jié)點移動速度變化下網(wǎng)絡能源效率的比較Fig.7 Comparison of network energy efficiency under the change of node movement speed

4 結(jié)束語

本文利用二次多項式和滑動窗口技術提出了一個新的網(wǎng)絡編碼算法(QPPSW-NC)，設計了一個QPPSW-NC解碼復雜度的分析模型，使用網(wǎng)絡仿真軟件NS2對QPPSW-NC算法進行性能分析，并從網(wǎng)絡吞吐量、編碼開銷、數(shù)據(jù)包傳輸時延、能源消耗和能源效率等方面進行評估.仿真結(jié)果表明，QPPSW-NC算法可以提高網(wǎng)絡的可靠性、提高網(wǎng)絡的性能.