中圖分類號：TP393.0 文獻(xiàn)標(biāo)志碼：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)絡(luò)中，數(shù)據(jù)在節(jié)點間經(jīng)過多跳轉(zhuǎn)發(fā)傳輸，傳統(tǒng)的數(shù)據(jù)路由思想是存儲和轉(zhuǎn)發(fā)[1-2].RAhlswede等[3]以最大流-最小割理論為依據(jù)提出網(wǎng)絡(luò)編碼的概念，隨后出現(xiàn)更多研究以提升網(wǎng)絡(luò)性能和節(jié)省帶寬.網(wǎng)絡(luò)編碼能夠利用多跳鏈路的中間節(jié)點對數(shù)據(jù)進(jìn)行處理后再轉(zhuǎn)發(fā)，以此減少數(shù)據(jù)傳輸次數(shù)、減少網(wǎng)絡(luò)資源消耗和提升數(shù)據(jù)吞吐量[4].

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

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

1網(wǎng)絡(luò)模型

1.1 分簇模型

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

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

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

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

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

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

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

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

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

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

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

2.2 確定編碼鏈路

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

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

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

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

2.3 編碼流量分配

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

結(jié)合上述假設(shè)，能得到關(guān)系：

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

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

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

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

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

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

3 仿真實驗與結(jié)果分析

本文提出的基于遺傳模擬退火的分簇編碼流量分配方法標(biāo)記為CFDGSA，采用MatlabR2023b軟件進(jìn)行仿真分析，對比算法包括MCACR[9]和 ED-ACO^[10] .為了適應(yīng)大數(shù)據(jù)量的無線傳感器數(shù)據(jù)傳輸，設(shè)置網(wǎng)絡(luò)區(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ù)包平均傳輸速率結(jié)果分析

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

3.2 端到端的平均時延結(jié)果分析

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

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

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

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

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

4結(jié)語

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

參考文獻(xiàn)：

[1］裴慶慶.基于多傳感融合技術(shù)的自主巡邏智能預(yù)警機(jī)

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

[2］胡必玲，仝鈺，郭玉堂.改進(jìn)的無線傳感器網(wǎng)絡(luò)質(zhì)心定位算法[J].蘭州文理學(xué)院學(xué)報（自然科學(xué)版)，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)絡(luò)流量的異常檢測方法研究[D].蘭州：西北師范大學(xué)，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)絡(luò)路由優(yōu)化[J].河南工程學(xué)院學(xué)報（自然科學(xué)版)，2023，35(4):39-44.

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

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

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

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

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

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

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

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

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

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

[責(zé)任編輯：李 嵐]