基于遺傳模擬退火的編碼流量分配方法

中圖分類號：TP393.0 文獻標志碼：A

Coded Flow Distribution Method Based on Genetic Simulation Annealing

TAO Qi-hong (School of Computer and Information Engineering ，Bengbu University，Bengbu 23303O，Anhui，China)

Abstract:In the wireless sensor network，in order to solve the problem that the traditional multi-path routing cannot actively discover the coding opportunities and balance the load reasonably，a coded flow distribution method based on genetic simulation annealing is proposed. Firstly，clustering based on node data density is used，then the coding link and coding node are determined by reverse data flow，and finally the genetic simulation annealing is used to optimize the distribution of coding trafic. The simulation results show that the encoding opportunities of the proposed method are increased，the network performance is improved，and the overall coding performance is improved.

Key words:genetic simulation annealing； flow distribution; multipath routing;coding link

0 引言

無線傳感器網絡中，數據在節點間經過多跳轉發傳輸，傳統的數據路由思想是存儲和轉發[1-2].RAhlswede等[3]以最大流-最小割理論為依據提出網絡編碼的概念，隨后出現更多研究以提升網絡性能和節省帶寬.網絡編碼能夠利用多跳鏈路的中間節點對數據進行處理后再轉發，以此減少數據傳輸次數、減少網絡資源消耗和提升數據吞吐量[4].

COPE算法首次引入機會偵聽，采用流間網絡編碼傳輸方式，能夠提供編碼更多數據包的可能性，但其有效范圍只有兩跳[5].文獻[6]結合網絡拓撲結構和通信距離，提出基于遺傳算法優化構建傳輸路徑的方法，提升路徑尋找的速度和網絡壽命，但是對數據吞吐量提升有限.文獻[7]針對傳統算法簇頭數量不等且分布不合理的問題，采用靠近質心的策略，同時利用分布式簇頭選舉方法提升算法效率，該方法能均衡節點能耗，但是對網絡的負載均衡效果一般.文獻[8]采用模糊密度峰值聚類算法對分簇過程進行優化，通過粒子群優化傳輸路徑，使網絡生命周期進一步提升，但是未能進一步優化數據傳輸效率.文獻[9針對數據傳輸可靠性差的問題，通過在狀態轉移函數中引入動態補償因子，在膜計算中引入最優路徑衡量公式，該算法在數據可靠性和網絡節能方面有較大提升.文獻[10]綜合考慮了丟包率、延遲、剩余能量和可用存儲4個參數，對分簇過程進行優化，在狀態轉移概率公式計算中引入蟻群算法，選擇最優下一跳路徑，在延遲上滿足服務質量需求，但是對網絡節能和負載均衡的優化欠佳.

針對上述問題，本文提出一種基于遺傳模擬退火的編碼流量分配方法.該方法為提升編碼機會發現效率，采用基于節點數據密度的策略形成分簇；通過維護節點數據量流表和簇內數據流表，利用簇內逆向數據流確定編碼鏈路和編碼節點；將編碼數據流分配在編碼鏈路，采用遺傳模擬退火優化編碼流量分配.

1網絡模型

1.1 分簇模型

將傳感器節點分簇有助于降低網絡數據包轉發路徑選擇的復雜度，提升編碼效率[11-12].區域內的節點采用基于節點數據密度的分簇策略，選取一個節點作為簇頭節點 CH_i ，將附近距離1跳的節點 N_i 劃分為一個簇 ，數據包在簇內和簇間依然通過多跳的形式轉發，簇頭節點選取過程采用周期性輪轉機制，保證網絡中能耗均衡，分簇模型如圖1所示.

1.2簇內數據異或編碼轉發模型

假設一個簇內的數據流由節點 N₁ 、 N₂ 和 N₃ 承擔，若采用傳統存儲轉發的方式，數據包 x_a 由節點 N₁ 發送至節點 N₃ ，數據包 x_b 由節點 N₃ 發送至節點 N₁ ，共需4個傳輸時隙和2個數據包，假設傳輸總用時為4秒，則數據包傳輸速率為0.5包每秒，傳統存儲轉發過程如圖2所示.

如果節點 N₂ 在收到數據包 x_a 和 |x_b| 后進行異或編碼，將生成的編碼數據包 同時廣播發送至節點 N₁ 和 N₃ ，則總傳輸次數減少1次，數據包傳輸速率為2/3包每秒，異或編碼轉發過程如圖3所示.

2基于遺傳模擬退火的編碼流量分配方法

針對上述網絡模型，本文方法采用分簇策略，利用簇內逆向數據，采用遺傳模擬退火優化編碼流量分配.

2.1基于節點的數據密度分簇

節點 i 第 r 輪的節點數據密度可表示為

其中： NPF_i(r) 為節點 i 第 r 輪轉發的數據包數量； NPF_ij(r) 為距離節點 i 只有1跳的節點 j 第r 輪轉發的數據包數量； n 為距離節點 i 只有1跳的節點總數.

節點轉發的數據包數量越多，潛在的編碼機會越多，為了提升編碼機會發現效率，節點 i 第 r +1 輪的選簇參數可表示為

其中： REC_i 為當前節點剩余能量百分數；ECEC_i(r) 為 r 輪節點消耗的能量百分數.如果節點 i 的選簇參數大于閾值 T ，則該節點成為簇頭節點.分簇成功后簇頭節點設置定時器，定時結束后廣播輪轉分簇請求，開始下一輪分簇過程.

2.2 確定編碼鏈路

簇內節點需要維護節點數據流表，包括下一跳節點號、源簇號和目的簇號，并且定時發送給簇頭節點，其中下一跳節點號僅包括簇內節點，參數如表1所列.簇頭節點需要根據節點數據流表維護簇內數據流表，包括源簇號、目的簇號、流經節點和流經節點數，參數如表2所列.

簇頭節點對簇內節點提供的節點數據流表進行篩選和匯總，將源簇號和目的簇號相反的數據流信息保存在簇內逆向數據流表中，只有這部分數據流存在簇內潛在編碼可能性.對于簇內數據流表中，源簇號和目的簇號相反且流經節點數大于等于3的數據流存在編碼機會.根據表1和表2的數據，得到在簇 C₂ 內的流量如圖4所示.

圖4中，鏈路 N₁-N₂-N₃ 承載簇 C₁ 至簇C₃ 的數據流量 L_A ，方向標記為正向；鏈路 N₆ 一

N₅-N₄ 承載簇 C₃ 至簇 C₁ 的數據流量 L^′_B ，方向標記為逆向，互為簇內逆向數據流，滿足上述簇內編碼條件，將鏈路 N₁-N₂-N₃ 標記為編碼鏈路A ，鏈路 N₆-N₅-N₄ 標記為編碼鏈路 B

2.3 編碼流量分配

對于滿足簇內編碼條件的數據流，在編碼鏈路上分配編碼流量，能夠在簇內節點處創造編碼機會.以2.2節描述的編碼鏈路為例，簇內節點N₂ 和 N₅ 均具有編碼機會，簇內流量分配后，標記簇 C₁ 至簇 C₃ 的數據流量在編碼鏈路 A 的正向流量為 NL_A 、逆向流量為 NL_A^′ ，標記簇 C₃ 至簇 C₁ 的數據流量在編碼鏈路 B 的正向流量為 NL_B 、逆向流量為 NL_B^′ ，編碼流量分配過程如圖5所示.

結合上述假設，能得到關系：

其中： FC 為正向流量分配系數； IC 為逆向流量分配系數.

將上述分配系數取0.5作為初始種群，利用遺傳算法[13-14]進行優化，在每輪遺傳算法最后使用模擬退火[15-16]算法提升最優解計算速度.為了進一步提升網絡整體吞吐量，適應度函數 fit 計算過程為

其中： PTR_i 為節點 i 的數據包傳輸速率； n 為網絡中節點總數量.

選擇操作能夠保證當前種群中較為優秀的個體基因進入下一代種群，為了加快算法收斂，對精英個體直接保留進入下一代種群，剩余個體通過輪盤賭的方式，按照適應度概率選取.交叉操作能夠提升遺傳算法的搜索能力，為了提升交叉效率并保證算法的低復雜度，采用按適應度由高到低對個體排序，相鄰個體單點交叉的方式，交叉位置選擇在個體編碼的尾端，交叉概率為自適應.變異能夠改變個體編碼值，產生新的個體，采用固定變異算子，只改變個體編碼的固定一位，與交叉采用相同的自適應變異概率.

在遺傳算法每輪迭代的最后，對新種群采用模擬退火降溫逼近最優解.當降溫后，個體的適應度足夠優秀時，直接接受該個體；如果在降溫后個體適應度不夠優秀，則計算接受概率，舍棄不合格個體.當溫度未下降到預設值時，模擬退火過程持續，為保證模擬退火操作能夠更容易突破局部最優解，在降溫初期保證較大的接受概率，降溫末期時接受概率較小.退火溫度計算過程可表示為：

其中： 為第 r 輪的退火溫度； k 為溫度衰減系數.

3 仿真實驗與結果分析

本文提出的基于遺傳模擬退火的分簇編碼流量分配方法標記為CFDGSA，采用MatlabR2023b軟件進行仿真分析，對比算法包括MCACR[9]和 ED-ACO^[10] .為了適應大數據量的無線傳感器數據傳輸，設置網絡區域為正方形，邊長為 1 000m ，包含的節點數量范圍為 200～400 個，數據包大小為 500kb ，節點數據發送速率分別為 500 kbps、1 000 kbps 和 2 000 kbps.

3.1 數據包平均傳輸速率結果分析

MCACR算法利用膜計算的膜內和膜間運算并行能力，結合引入的最優路徑衡量公式，進行多路徑并行搜索獲取到最優的路徑，能夠提升網絡吞吐量.ED-ACO通過多標準參數，利用蟻群算法計算下一跳路徑，能夠提升數據包轉發速率和網絡服務質量.所提CFDGSA方法在分簇時考慮節點數據密度，主動發現編碼鏈路后優化流量分配，能夠進一步提升節點的數據傳輸效率.由仿真結果可知，在節點數據發送速率較低時，3種算法的吞吐量差距不大，但隨著節點數據發送速率逐漸變大，CFDGSA具有編碼傳輸的優勢逐漸體現.在節點數據發送速率達到最大時，CFDGSA相比MCACR和ED-ACO在數據平均傳輸速率上提升了 66.7% 和 25% .當網絡內數據量較大時，CFDGSA方法更能發揮作用.不同節點數據發送速率的數據，平均傳輸速率對比情況如圖6所示.

3.2 端到端的平均時延結果分析

MCACR通過改進信息素更新和路由節點修復能夠降低端到端的時延.ED-ACO能在鏈路質量較差時減少對應的負載任務，提升網絡時延能力.所提CFDGSA方法能夠分析簇間的數據流，采用編碼傳輸減少數據包傳輸次數，從而降低端到端的平均時延.不同節點數量端到端的平均時延對比情況如圖7所示.

由仿真結果可知，3種方法的曲線均呈現下凹狀.在節點數量增長初期，網絡中節點的增加給時延降低帶來的是正增益，在后期則相反.MCACR在節點數量為250個時最先達到最低時延，ED-ACO 和CFDGSA則分別在300 和350個時到達.在達到最低時延后，隨著節點繼續增多，數據包傳輸距離更長，CFDGSA方法端到端平均時延的增加更加趨于平緩，在數據量和節點數量較多的網絡中更能體現算法效率.

3.3節點能耗結果分析

MCACR融合膜計算與蟻群算法檢測路徑，能夠在一定程度上減少路由空洞和非必要能耗.ED-ACO利用狀態轉移概率提升預測概率，降低傳輸能耗.所提CFDGSA方法在分簇時考慮節點能耗狀態，通過編碼傳輸減少節點傳輸能耗，通過流量分配均衡網絡負載，進一步提升網絡生命周期.網絡剩余能量對比情況如圖8所示.

由仿真結果可知，MCACR在第150輪能耗歸零，CFDGSA方法能夠將網絡持續至198輪，相較于ED-ACO的172輪，提升了 15% .同時在能耗歸零前50輪內，CFDGSA方法的能耗均勻性也更好，說明本文方法更適應對網絡生命周期要求較高的應用場景.

4結語

針對傳統多路徑路由不能主動發現編碼機會和合理均衡負載的問題，提出了一種基于遺傳模擬退火的編碼流量分配方法，該方法通過節點分簇，降低發現編碼鏈路的難度，通過維護數據發送信息確定編碼鏈路和編碼節點，將負載分配在編碼鏈路，通過遺傳模擬退火優化編碼負載分配.實驗結果證明所提方法相比現有算法有效提升了數據傳輸效率，降低了節點能耗.今后研究中將充分考慮優化編碼等待策略，進一步提升算法效率.

參考文獻：

[1］裴慶慶.基于多傳感融合技術的自主巡邏智能預警機

奮八爾時研つ以いLJ」二川乂堙子阮子摳（日熱科學版)，2022，36(1):43-47.

[2］胡必玲，仝鈺，郭玉堂.改進的無線傳感器網絡質心定位算法[J].蘭州文理學院學報（自然科學版)，2022，36(2) :46-51.

[3] KATTI S，RAHUL H，HU W，et al. XORs in the air:practical wireless network coding [J]. ACM SIG-COMM Computer Communication Review，2006，36(4) :243-254.

[4]黎博寧.WSN中傳感器數據流及網絡流量的異常檢測方法研究[D].蘭州：西北師范大學，2023.

[5] CHACHULSKI S， JENINGS M， KATTI S， et al.Trading structure for randomness in wireless oppor-tunistic routing [J]. ACM SIGCOMM ComputerCommunication Review，2007，37(4) :169-180.

[6]丁凡，賀軍義，陳素霞，等.基于遺傳算法的無線傳感器網絡路由優化[J].河南工程學院學報（自然科學版)，2023，35(4):39-44.

[7］潘琢金，陳天毅，王傳云，等.一種適用于多基站環境的WSN分簇路由協議[J].計算機應用與軟件，2023，40(9) :99-103.

[8]張勇，呂黎明.基于模糊密度峰聚類和 PSO的WSN能量均衡算法[J].計算機仿真，2023，40（7）：418-422.

[9]高健文，黃友銳，徐善永，等.基于膜計算的蟻群算法在配電網WSNs中路由研究［J].重慶工商大學學報（自然科學版），2021，38(3)：50-57.

[10]杜佳軒，馬利亞，楊軍.基于QoS和分簇機制的WM-SNs 路由算法研究[J].計算機測量與控制，2017，25(2):196-200，207.

[11］張安楠.高速水聲通信中小時延、低功耗網絡編碼的設計與優化研究[D].北京：北京郵電大學，2023.

[12］徐靜.無線網絡中編碼感知機會路由協議研究[D].重慶：重慶郵電大學，2022.

[13]李姝，馮永新，張文波.遺傳算法與帶權搜索融合的QoS組播路由算法[J].小型微型計算機系統，2023，44(12):2752-2756.

[14］陳銘毓.基于深度學習的EON路由選擇策略及頻譜分配算法研究[D].南京：南京郵電大學，2023.

[15］蓋小賓.水下無線傳感器網絡的覆蓋優化與保持研究[D].濟南:齊魯工業大學，2023.

[16］范曉蕾.能耗優化的WSN層次型多跳路由協議研究[D].大連:大連理工大學，2022.

[責任編輯：李 嵐]