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

中圖分類號：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 引言

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

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

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

1網(wǎng)絡模型

1.1 分簇模型

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

1.2簇內(nèi)數(shù)據(jù)異或編碼轉發(fā)模型

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

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

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

針對上述網(wǎng)絡模型，本文方法采用分簇策略，利用簇內(nèi)逆向數(shù)據(jù)，采用遺傳模擬退火優(yōu)化編碼流量分配.

2.1基于節(jié)點的數(shù)據(jù)密度分簇

節(jié)點 i 第 r 輪的節(jié)點數(shù)據(jù)密度可表示為

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

節(jié)點轉發(fā)的數(shù)據(jù)包數(shù)量越多，潛在的編碼機會越多，為了提升編碼機會發(fā)現(xiàn)效率，節(jié)點 i 第 r +1 輪的選簇參數(shù)可表示為

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

2.2 確定編碼鏈路

簇內(nèi)節(jié)點需要維護節(jié)點數(shù)據(jù)流表，包括下一跳節(jié)點號、源簇號和目的簇號，并且定時發(fā)送給簇頭節(jié)點，其中下一跳節(jié)點號僅包括簇內(nèi)節(jié)點，參數(shù)如表1所列.簇頭節(jié)點需要根據(jù)節(jié)點數(shù)據(jù)流表維護簇內(nèi)數(shù)據(jù)流表，包括源簇號、目的簇號、流經(jīng)節(jié)點和流經(jīng)節(jié)點數(shù)，參數(shù)如表2所列.

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

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

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

2.3 編碼流量分配

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

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

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

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

其中： PTR_i 為節(jié)點 i 的數(shù)據(jù)包傳輸速率； n 為網(wǎng)絡中節(jié)點總數(shù)量.

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

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

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

3 仿真實驗與結果分析

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

3.1 數(shù)據(jù)包平均傳輸速率結果分析

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

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

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

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

3.3節(jié)點能耗結果分析

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

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

4結語

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

參考文獻：

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

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

[2］胡必玲，仝鈺，郭玉堂.改進的無線傳感器網(wǎng)絡質心定位算法[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中傳感器數(shù)據(jù)流及網(wǎng)絡流量的異常檢測方法研究[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]丁凡，賀軍義，陳素霞，等.基于遺傳算法的無線傳感器網(wǎng)絡路由優(yōu)化[J].河南工程學院學報（自然科學版)，2023，35(4):39-44.

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

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

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

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

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

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

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

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

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

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

[責任編輯：李 嵐]