基于HPSO的自適應(yīng)路由節(jié)點(diǎn)優(yōu)化部署策略

樊成鵬，張麗娜

(1.重慶華渝電氣集團(tuán)有限公司，重慶 400021；2.中北大學(xué) 信息與通信工程學(xué)院，太原 030051)

0 引言

近些年隨著無線通信技術(shù)的不斷進(jìn)步，在各個(gè)領(lǐng)域中對(duì)于無線通信網(wǎng)絡(luò)的應(yīng)用不斷增加，同時(shí)對(duì)于無線通信網(wǎng)絡(luò)的技術(shù)研究也在不斷發(fā)展。節(jié)點(diǎn)部署對(duì)于無線通信網(wǎng)絡(luò)的成本，通信功耗，通信質(zhì)量都有著不可忽視的影響[1,2]。好的節(jié)點(diǎn)部署策略可以使無線通信網(wǎng)絡(luò)有更低的成本，更低的功耗以及更好的通信質(zhì)量。

對(duì)于無線通信網(wǎng)絡(luò)，其結(jié)構(gòu)中包含了終端節(jié)點(diǎn)，路由節(jié)點(diǎn)及匯聚節(jié)點(diǎn)[3]。對(duì)于終端節(jié)點(diǎn)在網(wǎng)絡(luò)中的位置，主要取決于終端節(jié)點(diǎn)所需要實(shí)現(xiàn)的功能。例如在農(nóng)業(yè)物聯(lián)網(wǎng)的節(jié)點(diǎn)部署過程中，對(duì)于溫度監(jiān)測(cè)終端節(jié)點(diǎn)的部署與光強(qiáng)監(jiān)測(cè)終端節(jié)點(diǎn)的部署有不同的部署條件，其主要取決于農(nóng)作物所處環(huán)境特點(diǎn)，即在部署過程中，此類終端節(jié)點(diǎn)部署的主要影響因素即實(shí)際應(yīng)用的環(huán)境特點(diǎn)。無線通信網(wǎng)絡(luò)中的匯聚節(jié)點(diǎn)主要功能是對(duì)于整體網(wǎng)絡(luò)中的數(shù)據(jù)進(jìn)行處理，相較于終端節(jié)點(diǎn)或匯聚節(jié)點(diǎn)，一般匯聚節(jié)點(diǎn)僅有1個(gè)或幾個(gè)即可實(shí)現(xiàn)對(duì)全部網(wǎng)絡(luò)內(nèi)數(shù)據(jù)的處理，所以在一般的無線通信網(wǎng)絡(luò)中，都是以匯聚節(jié)點(diǎn)的位置為中心進(jìn)行其他節(jié)點(diǎn)的部署。

對(duì)于節(jié)點(diǎn)部署的過程，目前相關(guān)學(xué)者主要采用智能算法進(jìn)行尋優(yōu)，具體算法包括人工免疫算法(AIA,artificial immune algorithm)、遺傳算法(GA,genetic algorithm)等。此類方法中節(jié)點(diǎn)坐標(biāo)獲取與功能劃分或組網(wǎng)通信是分段完成的，無法同時(shí)將兩部分協(xié)同尋優(yōu)，也正由于此，此類方法的局限性趨于明顯[4]。

一個(gè)完整高效的無線通信網(wǎng)絡(luò)的設(shè)計(jì)，不僅僅在于節(jié)點(diǎn)間通訊功能的實(shí)現(xiàn)，更重要的是需要完善的、穩(wěn)定的數(shù)據(jù)網(wǎng)絡(luò)[5]。對(duì)于無線網(wǎng)絡(luò)的設(shè)計(jì)，陳暢等針對(duì)網(wǎng)絡(luò)能耗和壽命問題，通過對(duì)無線通信網(wǎng)絡(luò)特征的多目標(biāo)優(yōu)化算法設(shè)計(jì)了一種傳感器節(jié)點(diǎn)智能部署方法，但其方法僅通過調(diào)整組網(wǎng)通信規(guī)則，并未對(duì)節(jié)點(diǎn)部署有進(jìn)一步優(yōu)化研究[6]。吳海燕等通過優(yōu)化圖論方法實(shí)現(xiàn)光傳感器節(jié)點(diǎn)的優(yōu)化部署，但算法中限制條件及因素過多，雖算法達(dá)到理想的尋優(yōu)結(jié)果，但算法效率降低[7]。陳欣等提出基于生物地理學(xué)優(yōu)化算法的節(jié)點(diǎn)部署策略，算法優(yōu)化后尋優(yōu)效率改進(jìn)，但該方法在節(jié)點(diǎn)數(shù)量變多時(shí)尋優(yōu)精度下降[8]。但上述研究中對(duì)于節(jié)點(diǎn)的部署，均以提升算法尋優(yōu)的效率或算法精度為優(yōu)化目標(biāo)，對(duì)節(jié)點(diǎn)的基礎(chǔ)部署方法均未研究。宋偉奇等針對(duì)無線組網(wǎng)的能耗問題和數(shù)據(jù)擁塞問題，通過優(yōu)化網(wǎng)絡(luò)節(jié)點(diǎn)可靠性權(quán)值提出了一種網(wǎng)絡(luò)節(jié)點(diǎn)的優(yōu)化方法，但算法中權(quán)值需要每次針對(duì)特定應(yīng)用背景進(jìn)行設(shè)置，不具有通用性[9]。韋運(yùn)玲等針對(duì)傳感器網(wǎng)絡(luò)特性而影響其壽命的問題，設(shè)計(jì)了一種基于自適應(yīng)人工免疫網(wǎng)絡(luò)算法的無線通信網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，雖延長(zhǎng)了網(wǎng)絡(luò)壽命，但該結(jié)構(gòu)對(duì)實(shí)際傳輸應(yīng)用背景過于限制[10]。Maheswari等通過分析F-SCH(Fuzzy based Super Cluster Head)方法，提出了一種利用模糊控制結(jié)合自適應(yīng)結(jié)構(gòu)提高整體網(wǎng)絡(luò)節(jié)點(diǎn)的有效壽命的方法，但該方法需在超大規(guī)模傳感網(wǎng)內(nèi)進(jìn)行應(yīng)用[11]。

上述方法對(duì)于無線通信網(wǎng)絡(luò)的部署策略都有一定的優(yōu)化研究，但對(duì)于空間自適應(yīng)節(jié)點(diǎn)的部署均未涉及[12-16]。同時(shí)上述方法的算法在優(yōu)化過程以犧牲算法的準(zhǔn)確性來提升算法效率。雖然目前已有眾多方法用于優(yōu)化無線通信網(wǎng)絡(luò)，但在路由節(jié)點(diǎn)的控制上尚未有明確的優(yōu)化方法[16-19]。本文提出一種基于優(yōu)化混合粒子群算法(HPSO,hybrid particle swarm optimization,)結(jié)合自適應(yīng)路由節(jié)點(diǎn)部署策略(ADS,adaptive routing node deployment strategy,)的路由節(jié)點(diǎn)部署方法。

1 算法模型

1.1 路由節(jié)點(diǎn)部署成本模型

相關(guān)學(xué)者對(duì)于無線通網(wǎng)絡(luò)中的路由節(jié)點(diǎn)也有所研究[19]。本文針對(duì)無線通信網(wǎng)絡(luò)中如何實(shí)現(xiàn)終端到匯聚節(jié)點(diǎn)所需部署最低成本的路由節(jié)點(diǎn)為算法尋優(yōu)目標(biāo)。其中路由節(jié)點(diǎn)部署成本主要包括部署的通信距離成本和節(jié)點(diǎn)組網(wǎng)關(guān)系功耗成本。其部署的總成本計(jì)算式如下：

P=α·Px+β·Pc

(1)

1.1.1 路由節(jié)點(diǎn)部署通信距離成本模型

路由節(jié)點(diǎn)部署過程中的成本，主要包含節(jié)點(diǎn)成本，部署后的通信功耗成本，節(jié)點(diǎn)部署成本即無線模塊的基礎(chǔ)成本與數(shù)量的積。通信功耗成本包括通信距離產(chǎn)生的成本及組網(wǎng)關(guān)系產(chǎn)生的成本。

無線通信網(wǎng)絡(luò)中的組網(wǎng)可以分為一級(jí)通信關(guān)系和二級(jí)通信關(guān)系。一級(jí)通信關(guān)系即路由節(jié)點(diǎn)與路由節(jié)點(diǎn)間的組網(wǎng)和路由節(jié)點(diǎn)與匯聚節(jié)點(diǎn)間的組網(wǎng)。二級(jí)通信關(guān)系即終端節(jié)點(diǎn)與路由節(jié)點(diǎn)的組網(wǎng)。

節(jié)點(diǎn)間的通信距離計(jì)算式如下：

(2)

一級(jí)、二級(jí)通信關(guān)系單位距離的功耗分別是R1d、R2d，則，節(jié)點(diǎn)間距離為dx時(shí)，一級(jí)、二級(jí)通信關(guān)系產(chǎn)生的功耗如下式：

(3)

(4)

通信距離產(chǎn)生總計(jì)成本如下式：

(5)

1.1.2 路由節(jié)點(diǎn)部署組網(wǎng)結(jié)構(gòu)功耗成本模型

無線網(wǎng)絡(luò)中組網(wǎng)關(guān)系如圖1所示。

圖1 組網(wǎng)關(guān)系示意圖

如圖1中所示，組網(wǎng)節(jié)點(diǎn)結(jié)構(gòu)主要包括匯聚節(jié)點(diǎn)、路由節(jié)點(diǎn)和終端節(jié)點(diǎn)[20-22]。通信結(jié)構(gòu)主要分為一級(jí)通信關(guān)系和二級(jí)通信關(guān)系。匯聚節(jié)點(diǎn)僅與路由節(jié)點(diǎn)進(jìn)行通信，本文假設(shè)每一個(gè)一級(jí)通信關(guān)系傳輸對(duì)于發(fā)送節(jié)點(diǎn)的功耗是R1si，接收節(jié)點(diǎn)的功耗是R1ri。每一個(gè)二級(jí)通信關(guān)系傳輸對(duì)于節(jié)點(diǎn)的功耗是R2si，接收功耗是R2ri。假設(shè)共計(jì)有n1個(gè)一級(jí)通信關(guān)系，n2個(gè)二級(jí)通信關(guān)系。

則該網(wǎng)絡(luò)組網(wǎng)結(jié)構(gòu)一級(jí)通信關(guān)系產(chǎn)生的功耗如下式：

R1c=ω1c·n1·(R1si+R1ri)

(6)

則該網(wǎng)絡(luò)組網(wǎng)結(jié)構(gòu)一級(jí)通信關(guān)系產(chǎn)生的功耗如下式：

R2c=ω1c·n2·(R2si+R2ri)

(7)

則該網(wǎng)絡(luò)組網(wǎng)結(jié)構(gòu)產(chǎn)生的總功耗如下式：

R=R1c+R2c

(8)

設(shè)組網(wǎng)結(jié)構(gòu)一級(jí)通信關(guān)系單位功耗產(chǎn)生的成本是Pc1，二級(jí)通信關(guān)系單位功耗產(chǎn)生的成本是Pc2。則組網(wǎng)結(jié)構(gòu)總計(jì)成本為：

Pc=ac·Pc1·R1c+bc·Pc2·R2c

(9)

路由節(jié)點(diǎn)部署過程中的成本，主要包含節(jié)點(diǎn)成本，部署后的通信功耗成本。

1.2 路由節(jié)點(diǎn)通信距離限制關(guān)系模型

本文在路由節(jié)點(diǎn)部署時(shí)，通信距離應(yīng)滿足數(shù)據(jù)發(fā)送接收雙方節(jié)點(diǎn)最小通信距離限制，通信限制關(guān)系模型如下式：

Dh>Dr>Dz

(10)

即匯聚節(jié)點(diǎn)覆蓋范圍最大，其次是路由節(jié)點(diǎn)，終端節(jié)點(diǎn)通信距離限制范圍最小。

1.3 路由節(jié)點(diǎn)通信限制關(guān)系模型

在進(jìn)行路由節(jié)點(diǎn)部署時(shí)，對(duì)于一個(gè)節(jié)點(diǎn)，其所無線通信節(jié)點(diǎn)數(shù)是k，則：

對(duì)于一個(gè)匯聚節(jié)點(diǎn)，與其通信的節(jié)點(diǎn)數(shù)量如下：

0

(11)

對(duì)于一個(gè)路由節(jié)點(diǎn)，與其通信的節(jié)點(diǎn)數(shù)量如下：

0

(12)

對(duì)于一個(gè)終端節(jié)點(diǎn)，與其通信的節(jié)點(diǎn)數(shù)量如下：

kz=1

(13)

即每一個(gè)終端節(jié)點(diǎn)僅能和一個(gè)路由節(jié)點(diǎn)通信。

1.4 路由節(jié)點(diǎn)部署通信質(zhì)量評(píng)價(jià)模型

無線通信網(wǎng)絡(luò)中，對(duì)于通信質(zhì)量的評(píng)估，本文通過自由空間損耗進(jìn)行比較。自由空間損耗主要與通信頻率和通信距離有關(guān)。在本文無線通信網(wǎng)絡(luò)中，一級(jí)通信關(guān)系采用同一頻率，二級(jí)通信關(guān)系也采用同一頻率。故主要用通信距離計(jì)算自由空間損耗。

本文中定義每一個(gè)通信關(guān)系間的自由空間損耗如下式：

L=20lg(d+dL)

(14)

式中，dL是自由空間損耗常數(shù)。

2 算法設(shè)計(jì)

本文方法以ADS進(jìn)行節(jié)點(diǎn)坐標(biāo)部署，并采用優(yōu)化HPSO進(jìn)行部署迭代尋優(yōu)，最終得到最低成本條件下的最佳部署結(jié)果。總體流程圖如圖2所示。

圖2 路由節(jié)點(diǎn)部署總體流程圖

2.1 優(yōu)化HPSO算法設(shè)計(jì)

2.1.1 HPSO設(shè)計(jì)

本文中HPSO主要基于PSO并加入GA算法特性，使其在迭代過程中也具有交叉，變異等過程，從而更快速尋優(yōu)。基于優(yōu)化HPSO的流程圖如圖3所示。

圖3 優(yōu)化HPSO流程圖

算法中，適應(yīng)度函數(shù)計(jì)算式如下(在進(jìn)行粒子種群進(jìn)化時(shí)，適應(yīng)度值越低則粒子越優(yōu)秀)：

(15)

式中α為本方法中在計(jì)算適應(yīng)度函數(shù)時(shí)限制的最高成本。K是適應(yīng)度常數(shù)。

HPSO粒子更新表達(dá)式如下：

(16)

(17)

上式即在常規(guī)粒子群算法基礎(chǔ)上，使慣性權(quán)重線性遞減，隨著迭代的進(jìn)行，算法搜索越來越精確。

2.1.2 HPSO淘汰機(jī)制

本方法中采用基于優(yōu)化HPSO結(jié)合ADS。本文HPSO在優(yōu)化過程中，隨著算法中各個(gè)粒子個(gè)體適應(yīng)度值的不斷趨優(yōu)，在算法中采用了淘汰機(jī)制，如下式：

(18)

即子代適應(yīng)度值優(yōu)于父代時(shí)，子代保留，否則，子代淘汰。在本方法中的淘汰機(jī)制中粒子種群進(jìn)化所需的淘汰比例式如下：

(19)

其中，W為每代中的淘汰比例，W0為淘汰個(gè)數(shù)最小閾值，n為當(dāng)前迭代的順序數(shù)；β用于控制在種群迭代過程中淘汰的數(shù)量隨迭代順序數(shù)變化水平；V為常數(shù)。

2.1.3 HPSO多樣性補(bǔ)充機(jī)制

每一代粒子在淘汰過后，種群多樣性迅速下降，本方法在下一代種群中加入按照一定淘汰比例的隨機(jī)生成全新粒子，以補(bǔ)充種群多樣性。

K=N·w

(20)

即在原有種群中加入P1到PK的個(gè)體，其中K與N的關(guān)系滿足w的正比例關(guān)系。

2.2 ADS算法設(shè)計(jì)

本方法中，ADS主要采用建立當(dāng)前節(jié)點(diǎn)可視空間范圍的方法。在進(jìn)行路由節(jié)點(diǎn)自適應(yīng)部署時(shí)，從終端傳感器節(jié)點(diǎn)開始，采取可視域確立下一節(jié)點(diǎn)的方法。從起點(diǎn)起依次進(jìn)行操作，在部署完節(jié)點(diǎn)后每次與終點(diǎn)進(jìn)行距離判斷，當(dāng)與終點(diǎn)距離大于閾值時(shí)繼續(xù)部署，直至距離終點(diǎn)的長(zhǎng)度小于閾值時(shí)將當(dāng)前節(jié)點(diǎn)直接與終點(diǎn)相連接。ADS具體步驟如下：

1)初始化相關(guān)參數(shù)，根據(jù)實(shí)際通信能力確定通信距離閾值。

2)在起點(diǎn)處建立自適應(yīng)節(jié)點(diǎn)部署可視域模型，確定算法內(nèi)節(jié)點(diǎn)的空間可視域。

3)在已確立的可視域內(nèi)建立可視域內(nèi)節(jié)點(diǎn)選擇模型，進(jìn)行第一個(gè)路由節(jié)點(diǎn)的部署。

4)從起點(diǎn)依次進(jìn)行所有路由節(jié)點(diǎn)的相鄰部署。每次進(jìn)行部署時(shí)，對(duì)當(dāng)前節(jié)點(diǎn)與終點(diǎn)的距離進(jìn)行計(jì)算。當(dāng)此距離大于節(jié)點(diǎn)通信最大距離時(shí)，繼續(xù)進(jìn)行下一節(jié)點(diǎn)的部署。

5)當(dāng)距離終點(diǎn)的距離小于最大通信距離時(shí)，則不再進(jìn)行繼續(xù)部署，當(dāng)前節(jié)點(diǎn)即為最后一個(gè)通信節(jié)點(diǎn)。

2.2.1 自適應(yīng)節(jié)點(diǎn)部署可視域模型

在已知當(dāng)前節(jié)點(diǎn)部署坐標(biāo)后，下一節(jié)點(diǎn)進(jìn)行自適應(yīng)部署過程時(shí)，需要在節(jié)點(diǎn)可視域內(nèi)進(jìn)行部署。路由節(jié)點(diǎn)的可視域如圖4所示。

圖4 節(jié)點(diǎn)可視域示意圖

可視域范圍如下式：

(21)

x2+y2+z2

(22)

即可視域內(nèi)最遠(yuǎn)坐標(biāo)小于節(jié)點(diǎn)有效通信距離。

2.2.2 可視域內(nèi)節(jié)點(diǎn)選擇模型

在已知當(dāng)前節(jié)點(diǎn)部署坐標(biāo)后，下一節(jié)點(diǎn)進(jìn)行自適應(yīng)部署過程時(shí)，需要在節(jié)點(diǎn)可視域內(nèi)進(jìn)行部署。

方法中通過當(dāng)前路由節(jié)點(diǎn)與匯聚節(jié)點(diǎn)的坐標(biāo)位置關(guān)系，先縮減可視域范圍，并依據(jù)節(jié)點(diǎn)實(shí)際可部署范圍建立可行點(diǎn)集。通過對(duì)可行點(diǎn)集內(nèi)啟發(fā)函數(shù)的計(jì)算，根據(jù)選擇概率確定下一節(jié)點(diǎn)的坐標(biāo)。縮小可視域范圍如圖5所示。

圖5 節(jié)點(diǎn)縮小后可視域示意圖

根據(jù)路由節(jié)點(diǎn)部署限制范圍得到的可行點(diǎn)集原理圖如圖6所示。

圖6 節(jié)點(diǎn)可視域內(nèi)可行點(diǎn)集示意圖

啟發(fā)函數(shù)如下式：

H(i,j,k)=D(i,j,k)w1·S(i,j,k)w2·Q(i,j,k)w3

(23)

式中，D(i,j,k)代表當(dāng)前節(jié)點(diǎn)到下一節(jié)點(diǎn)的距離，Q(i,j,k)代表下一節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)間的距離，S(i,j,k)計(jì)算式如下：

(24)

式中，di,i-1代表當(dāng)前節(jié)點(diǎn)可視域和上一節(jié)點(diǎn)可視域重合的范圍。在完成啟發(fā)函數(shù)的計(jì)算后，選擇概率計(jì)算方法如下;

(25)

由上式可以得到下一節(jié)點(diǎn)的具體部署坐標(biāo)。

3 實(shí)驗(yàn)與結(jié)果分析

本文實(shí)驗(yàn)硬件環(huán)境為Inter?CoreTMi5-4210M CPU @2.60 GHz，運(yùn)行內(nèi)存16 G。采用Matlab仿真平臺(tái)。

3.1 算法參數(shù)初始化設(shè)定

基于優(yōu)化HPSO算法結(jié)合ADS的初始化參數(shù)設(shè)定如表1所示。

表1 算法參數(shù)

3.2 結(jié)果與分析

實(shí)驗(yàn)節(jié)點(diǎn)包括49個(gè)終端傳感器和一個(gè)匯聚節(jié)點(diǎn)。部署區(qū)域?yàn)?00*200 m范圍，路由節(jié)點(diǎn)通信范圍最大為75 m，匯聚節(jié)點(diǎn)最大通信范圍100 m，終端節(jié)點(diǎn)最大通信距離50 m，空間路由節(jié)點(diǎn)部署如圖7所示。

圖7 空間路由節(jié)點(diǎn)部署圖

在上述實(shí)驗(yàn)的基礎(chǔ)上，本文分別采用ADS與GA和AIA與本文方法進(jìn)行對(duì)比試驗(yàn)[23-24]。

3種方法進(jìn)行三十次算法迭代后得到的通信距離變化過程如圖8所示。

圖8 通信距離變化過程圖

由圖8可得，3種方法在剛開始迭代時(shí)并未出現(xiàn)明顯差距，隨著迭代的進(jìn)行，本文方法較其他兩種方法通信距離更低，隨著迭代次數(shù)的增加，本文方法的尋優(yōu)精確度越來越高。

3種方法得到的一級(jí)通信關(guān)系、二級(jí)通信關(guān)系距離如圖9所示。

圖9 3種方法一級(jí)、二級(jí)通信關(guān)系圖

由圖9可得，較GA與AIA，本文方法的一級(jí)、二級(jí)通信關(guān)系的通信距離均是最小。

由表2數(shù)據(jù)可得，本文方法具有最低的自由空間損耗，即本文方法所部署得到的路由節(jié)點(diǎn)網(wǎng)絡(luò)結(jié)構(gòu)通信質(zhì)量較好。

表2 3種方法實(shí)驗(yàn)結(jié)果

本文方法相較于GA和AIA，在保證通信質(zhì)量的基礎(chǔ)上，路由節(jié)點(diǎn)部署成本可降低8%～10%，算法迭代效率(尋優(yōu)時(shí)間)可提升14%～33%。

4 結(jié)束語

近些年來，無線通信技術(shù)的不斷發(fā)展，致使了無線通信網(wǎng)絡(luò)的不斷成熟。無線通信網(wǎng)絡(luò)中，節(jié)點(diǎn)部署是影響其特性是否良好的關(guān)鍵因素之一。高效的節(jié)點(diǎn)部署可以降低網(wǎng)絡(luò)成本，提高網(wǎng)絡(luò)通信質(zhì)量。節(jié)點(diǎn)部署的核心即是以已知環(huán)境作為條件進(jìn)行最佳的網(wǎng)絡(luò)結(jié)構(gòu)尋優(yōu)。對(duì)于一個(gè)無線通信網(wǎng)絡(luò)，一般其匯聚節(jié)點(diǎn)位置最先確定，終端節(jié)點(diǎn)的部署主要取決于網(wǎng)絡(luò)功能與環(huán)境間的相互影響，則需要進(jìn)行部署的即為無線網(wǎng)絡(luò)內(nèi)的路由節(jié)點(diǎn)。

本方法首先用自適應(yīng)性的節(jié)點(diǎn)部署順序，將 HPSO進(jìn)行初始化處理，并加入淘汰機(jī)制有效提高了整體算法的尋優(yōu)效率。本方法較AIA和GA而言，降低了節(jié)點(diǎn)部署的成本條件下，提高了算法效率。同時(shí)本方法結(jié)果中通信負(fù)載大的路由節(jié)點(diǎn)較少，將總通信任務(wù)盡可能均勻分布，提高了節(jié)點(diǎn)壽命。