一種基于噴泉碼的異構網絡發包算法*

袁 靜 劉建航 董軒江 李世寶

（中國石油大學（華東）海洋與空間信息學院 青島 266580）

1 引言

在物聯網時代中，所有智能設備互聯已成為必然趨勢。在網絡空間中，由于不同的無線設備使用不同的無線通信標準，所以異構無線設備上是相互隔離、無法直接通信的。若需要各個系統的數據在服務器進行數據交換，需要共同訪問Internet［1，3～4，6］。為了實現異構無線設備之間直接通信［5］，提出了Cross-Technology Communication（CTC）。CTC 改變了傳統無線技術之間間接通信的情況。以往這類通信方式往往需要通過帶有多個無線電接口的網關實現，而這類通信方法需要增加進出網關的流量開銷，并且為了滿足不同用戶相互通信，經常需要購買網關等硬件實現復雜的網絡部署。

現有的CTC 不僅可以使不同的物聯網應用程序共存，還能夠共享介質以及物理空間中部署異構設備［1］（例如：WiFi、ZigBee、藍牙等）。然而在已有的CTC中，進行文件傳輸時所依據的TCP協議的重傳機制存在自身局限性：在傳輸協議的編碼中，需要將傳輸的文件分成K 個數據包進行傳輸。若在傳輸過程中發生了丟包則需要通知源節點哪些數據包需要重傳進行再一次傳輸。直至所有數據包都被無差錯的被接收端接收完成譯碼后停止發送。這種傳統的傳輸方式雖然可以以高概率完成譯碼，但是由于較低的傳輸效率使得傳輸時間過長，在一些多播場景中并不適用。特別是在已有的CTC 中（WiFi To ZigBee），當ZigBee 接收全部數據包并完成譯碼后需要向WiFi 發送端發送確認消息進行反饋。由于ZigBee技術自身的傳播距離短、周期性數據、間歇性數據等特征，需要多跳才能完成反饋，所以若存在較大的丟包率則會造成巨大時延導致系統傳輸效率較低。

綜上，本文在CTC的基礎上提出了通過使用噴泉編碼實現異構網絡傳輸，利用噴泉碼其丟包不敏感的特點減小重傳機會，與此同時，本文根據分析實驗數據得到數據傳輸的丟包情況與發送條件有關。為減小丟包率，本文提出了在不同場景下實現丟包率最小的條件與發包算法。

2 相關工作

2.1 CTC研究成果

為了解決物聯網設備呈指數增長的數量帶來的頻譜危機，提出了現有PMC［9］。PMC 發送端的設計目標是利用與WiFi 子載波重合的帶寬模擬窄帶ZigBee 信號，提高頻譜利用率。它是指在單一的WiFi 通道中對異構物聯網無線電進行并行多協議通信，從而充分提高頻譜利用率。通過WiFi和Zig-Bee 設備之間的重疊通道來模仿ZigBee 的OQPSK調制實現在WiFi信道中發送ZigBee信號，如圖1所示：WiFi通道6與四個ZigBee通道（即：16、17、18和19）重合。利用這7 個子載波來模擬ZigBee 的OQPSK 調制，同時保持其余57 個子載波的正常通信，如圖1所示。

圖1 ZigBee與WiFi信道重疊

根據CSMA 協議，在傳輸ZigBee 信號時，WiFi的信號傳輸必須停止，所以造成了頻譜浪費。因此，PMC 為實現WiFi與ZigBee 信號同時傳輸，利用QAM 的特定WiFi 子載波信號模擬ZigBee 的OQPSK 信號，即將所需的ZigBee 時域信號輸入FFT，選擇相應的QAM 星座點，若沒有遇到完全重合的QAM 點則考慮到Parseval stheorem［7］所給出的能量方程，結合傅里葉變換的先行性質，即可得出頻域量化引入的誤差方程［8］：

其中，u（t）是時域信號，v（t）是經過QAM 量化后的時間時域信號U（k）和v（k）為其相對應的階。所以將時域內的信號失真最小化等價于QAM 量化后頻率分量的總偏差的最小化，即利用QAM 仿真的本質是一個優化過程。此時將沒有重合的點選擇總歐氏距離的k 個QAM 點與期望信號的k 個FFT 點之間距離最近的QAM點即可。

綜上，通過在物理層通過在發送端用WiFi 信號來模擬ZigBee信號，實現混合信號的發送。由圖1 可知，WiFi 第6 信道與ZigBee 信道重合，輸入的ZigBee 信號利用DSSS 模塊生產的LUT 查找表可以實現輸出其所匹配的QAM 點［9］，根據所輸出的QAM 點和WiFi 數據中其他的QAM 進行快速傅里葉逆變換聚合形成混合信號：

最后，在WiFi 接收端不更改硬件的情況下，由于WiFi 和ZigBee 的碼率不同，傳統的WiFi 接收機無法對混合信號中模擬的ZigBee 信號進行解調。所以，通過周期性地從信號數據流中刪除相應Zig-Bee 數據，形成指定的WiFi 數據，得到所需的WiFi數據流。同時，在ZigBee 接收端接收到的模擬Zig-Bee 信號經過帶通濾波器得到帶內信號，并將該信號送入OQPSK 解調器。該解調器通過將載波發生器的信號相乘，將基帶信號與載波信號分離，然后跟蹤同相分量和正交分量的相位變化，從而確定ZigBee數據流。

這種利用信道重合改變發送方調制方式進行的數據傳輸方式的丟包率較大，而較大的丟包率會造成了較大的失敗譯碼率，該機制下的丟包對譯碼影響很大，所以增大了信道中的確認與重傳消息。為實現較高效率的傳輸及較高的譯碼率，對CTC系統中新型的編譯碼方案提出了要求。

2.2 噴泉碼算法

噴泉碼本身是一種碼率不受限制的糾刪碼［2］（rateless erasure codes），即從源符號編碼產生的編碼符號序列是無限的，未成功完成譯碼中的中間數據不會對原始數據譯碼產生影響［11］。噴泉碼通過源源不斷的產生編碼分組流z1，z2…，作為任意長度向量的輸入與輸出符號。當接收端接收到產生的k 個輸入符號（x1，x2，…，xk）后，每個輸出符號等于若干個隨機獨立選取的輸入符號的異或和［10］，如圖2 所示。用此編碼方式進行數據收發，可以根據接收情況決定發包數量。

由圖2可知，LT碼的譯碼過程是一個低復雜度的迭代譯碼法。首先任意選取一個度為1 的編碼分組，若不存在度為1 的編碼分組，則結束譯碼；若存在，則通過復制就可以解碼出與該編碼分組相鄰的數據。根據Tanner圖，將已經恢復的數據分組信息與相鄰的數據信息進行模二和運算，若在傳輸過程發生了數據包丟失，則可以根據接收到的相鄰編碼分組得到丟失數據，從而更新編碼分組的信息，并將相應的Tanner 對應的邊刪除并且無需關注具體是哪些數據包發生了丟失，如此往復，直到找不到度為1的編碼分而技術譯碼。

圖2 LT碼的Tanner圖

所以針對現有CTC系統丟包率較大，對丟包較為敏感的特點，本文提出了一種基于噴泉碼的異構網絡發包算法（A fountain code based heterogeneous network packet sending algorithm，FCSA）。在本中通過搭建了PMC 平臺作為數據傳輸的基礎，其次本文提出了通過改變發送端的編碼方式，在發送端采取噴泉編碼方式增大譯碼率，無需更改現有的硬件設施與譯碼方式。最后本文通過進行多次數據傳輸的測試總結出影響丟包率的因素，并通過改變發送端發送策略從而使得丟包率達到最小。與已有算法相比，本文提出的算法可以明顯減小丟包率，使得傳輸系統有較大的的信道利用率與較高的譯碼率。

3 基于噴泉碼的異構網絡發包算法

3.1 算法思想

本節主要介紹FCSA 的主要思想，以及在CTC平臺進行實驗后對實現丟包率達到最小時的總結。首先，通過使用開銷較小的LT 碼對發送端進行編碼，假設接收節點將發送K 個原始數據包，根據度分布式（3）表明，在每個迭代過程中必有一個節點度為1，所以在理想情況下，孤子分布的度函數為

其次，為了保證接收器在接收到足夠數據包后進行解碼，每個疊戴過程至少應有一個度為1 的數據包［12］。若δ為接收機無法解碼原始數據的概率，則S=cloge(K′/δ)，有此可知，每次迭代過程中保證度數為1的數量為

根據輸出的混合信號可得，當傳統的WiFi 接收方接收到PMC 發送端發出的混合信號時，部分子載波包含WiFi 數據流，其余部分包含了ZigBee數據流。所以，我們在WiF端采取了周期性的刪除ZigBee 數據流從而提取出WiFi 數據流的方法，形成傳統的傳統的WiFi接收器指定的WiFi信號：

本文對丟包率的估算是指在傳輸過程中數據包丟失的數量占所發送的數據組的比率，其本身是用于衡量無線信道性能的重要指標，至今已經進行了許多針對估計丟包概率的相關研究［13～16］。本文根據現有的信道評估技術，利用接收端估計SNR（信噪比）［17］進行信道質量估計，通過式子表達每bit的能量比（Eb/N0）：

其中，Rb代表比特率，B 是信道帶寬，經過數字調制之后，采用低密度奇偶校驗（LDPC）編碼進行信道解碼，接收機解碼失敗概率可表示為

最后，根據本文在不同距離下測得的最小丟包率的匯總，找到不同距離下可以實現在該距離下的最小丟包率的對應發送周期、增益，對該周期、增益進行數據匯總、分析、模擬后得出不同距離下實現最小丟包率的發包條件。

3.2 實驗設置

我們在TelosB 平臺上，利用一個USRP 與三個ZigBee開發板實現了PMC模型，如圖3所示。其中，USRP 的型號為NI USRP-2932，通過本型號USRP 生成符合IEEE 802.11 標準下的WiFi 數據包，利用WiFi 與ZigBee 的重疊信道發送數據包至ZigBee 平臺。本實驗采用WiFi 的第6 信道和ZigBee 網絡的第16 信道來構建數據傳輸通道。本實驗通過調整發送周期、增益與距離變量，將其都作為可控開關，并進行測試與對其分別進行說明。實驗每次發送1000 個數據，測得每次發送后的接收情況，求得不同因變量下的丟包率，并對其進行分析。由于本設備在設置增益時，會產生接收信號振幅隨頻段和設備之間的變化而變化，所以本實驗全程在2.4GHz與相同的三個接收端進行。

圖3 實驗場景

3.3 實驗結果

3.3.1 距離的影響

本節介紹了當發送端與接收端處于不同距離下時對丟包率的影響。通過圖4 可得，隨著距離的增加，最大丟包率總體呈現上升趨勢，其次，由于ZigBee本身的短距離傳輸特性，經測量在10m～13m之間會有一次丟包率的突增現象。以12m為例，當發送端與接收端相距12m 時，無論增益如何變化，都會使得丟包率發生增加，所以在實際布置ZigBee節點時可以盡量避免該距離區間。

圖4 距離對丟包率的影響

3.3.2 增益的影響

本節介紹了當發送端與接收端增益不同時對最大丟包率的影響，利用USRP 調整發送增益，對比分析得到如下結論：本文選取0dB、16dB 和31dB三種增益進行實驗，如圖所示。根據圖5 可得，隨著增益的增加，最大丟包率明顯減小，例如當增益為0dB 時，平均丟包率為21.81%，當增益增加到16dB 時，平均丟包率減小至7.59%，可見增加發送增益可以明顯減小丟包率，例如，當發送端與接收端相距40m 時，當發送增益為16dB 時，最大丟包率為5.83%，增益增加至31dB 時，最大丟包率僅為2.70%。但是為了減小丟包率一味增加增益不一定會使丟包率減小，例如當發送端與接收端相距1m時，最大丟包率由于增益的增加沒有減小反而有所增加。由此可知，在距離一定的情況下，增加一定的增益可以明顯減小丟包率，但是不斷增加增益不一定會使得丟包率下降，反而有可能會使得丟包率比較小增益時增大。同時，由圖5 可知，較大的增益甚至可能會使得丟包率增加，所以為減小丟包率盲目增加增益會使得傳輸系統很不穩定，無法控制數據傳輸質量。

圖5 增益對丟包率的影響

3.3.3 周期的影響

本節介紹了當發送端與接收端周期不同時對丟包率的影響情況，由于本文中所述實驗進行測試次數較多，而對于數據傳輸過程中所能影響數據丟失的因素也比較多，所以發送周期的影響比較復雜。本節將分為三個部分進項闡述：

1）當發送端與接收端之間采取0dB 增益進行數據傳輸的時候，如果距離越近發送周期越小，可以減小丟包率，如圖6 所示。例如當發送端與接收端相距1m 時，若發送周期僅為25ms則丟包率僅為0.42%，較小發送周期對較遠距離并不友好，例如當發送端與接收端相距25m 時，若扔采取25ms 作為發送周期，則丟包率可高達16.27%，較大的數據丟失會嚴重影響網絡質量。所以較大傳輸距離的情況下應適當增加發送周期從而減小丟包率。

圖6 0dB時周期對丟包率的影響

2）當增益增加至16dB 時，距離對丟包率的影響遠遠小于增益對丟包率的影響。通過實驗可得，發送周期變小使得不同距離下的最大丟包率增多，但是并不代表較小的發送周期一定帶來大丟包率。例如當發送端月接收端相距25m時，發送周期為25ms 的丟包率僅為0.29%。當發送端與接收端相距12m，發送周期為10ms 時，這在實際應用場景中是一個很小的發送功率，但是此時的丟包率僅為0.38%。增益變大時發送周期越短并不意味著丟包率大，相反有時可以帶來更大的收益，使發送速率快并且很系統穩定，使得網絡性能大幅提升。尤其是超過12m 之后，丟包率比增益為0dB 時明顯減小，所以當距離增大時可以適當增加增益來減小丟包。

圖7 16dB時周期對丟包率的影響

3）通過圖8 我們可以對比出，相對于增益為16dB 的情況，當增加增益至31dB 時，整個網絡傳輸較不穩定。由圖8 可知，是當發送端的發送周期為50ms 時，發送端與接收端相距12m 的最大丟包率遠大于50m時的最大丟包率，所以當收發兩端相距很遠時，可以通過找到一個適宜的發送周期，使整個傳輸系統丟包率減小，例如當距離增大至50m時，發送周期提高至150ms 才可以實現最佳發送，剩下其余情況丟包率都高于該種情況。

圖8 31dB時周期對丟包率的影響

3.4 最小丟包率走勢

通過實驗對比我們發現，距離、增益與周期都是可以影響數據傳輸的重要因素。綜上所述，影響丟包的因素是多方面的，在傳感器網絡中，由于很多節點是無法移動的，所以通過調節增益與發送周期可實現網絡快速有效的傳播。最后，根據本文通過細化距離，在等差條件下測得的最小丟包率的匯總，如圖9所示。

圖9 等差距離下的最小丟包率

我們找到對應的發送周期，對該周期進行數據分析后得出不同距離下的最佳發送周期：當距離小于5m，增益小于等于16dB 時，發送端以任意發送周期都可達到0 丟包率；當距離大于5m，增益為31dB時，實現最小丟包率的最佳發送周期為

當發送端大于14m，增益為31dB 時，最佳發送周期為

其中，Pe為周期（單位：ms），d為距離（單位：m）。

4 實驗性能分析

在CTC 算法中，常見的性能指標包括吞吐量、誤碼率、時延和丟包率等。本文通過實際實驗，利用usrp發送數據包，普通商用ZigBee開發板進行廣播接收，測得噴泉編碼下利用本文所提FCSA 每次發送1000 個數據包的丟包率與時延，并與已有PMC平臺作為參照進行分析對比。

由圖10 可知當發送端與接收端采用增益為0dB 時，最大的丟包率也僅為13.32%，此時兩者相距“不穩定距離”12m。其次除了相距50m 時丟包率達到了10.69%以外，通過采用本文所提發包算法均可使丟包率低于2%。當增大發送端增益至16dB 時可以明顯減小數據傳輸過程的丟包率，此時在本文算法下的最大丟包率僅為相距50m 時的6.29%，同時其他情況均不發生丟包現象。當發送端調整增益至31dB 時，最大丟包率不足1%，并且此時發送端與接收端之間的距離為50m。

圖10 FCSA不同增益下的丟包率

圖11顯示了本文所提算法與PMC之間丟包率的對比，可以看出在PMC 平臺采用FCSA 算法后可以明顯降低丟包率，通過計算可得，發送端采用FCSA 算算法后，丟包率可減小至少66%以上。同時，由于丟包率的減小提升了系統的吞吐量，由圖12 可以知，在PMC 的基礎上，增加FCSA 算法可明顯提高吞吐量。

圖11 丟包率對比

圖12 吞吐量對比

5 結語

近幾年來，隨著物聯網設備不斷呈爆炸式增長，實現異構物聯網通信成為了必然趨勢。本文基于PMC 平臺設計了一種更高效的異構物聯網通信技術，通過采用噴泉編碼中成熟的LT 技術進行編碼，在實驗中測得了在所提編碼下的實現丟包率最小值的最優解。最后本文在所得數據中進行分析與總結得到FCSA算法相比較CSMA甚至PMC皆可明顯減小丟包率，同時很大程度提升了系統吞吐量。本文后續將繼續在此基礎上進行更多測試與探究，以期進一步提升該系統性能。