樊成鵬，張麗娜

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

0 引言

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

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

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

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

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

1 算法模型

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

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

P=α·Px+β·Pc

(1)

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

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

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

節(jié)點間的通信距離計算式如下：

(2)

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

(3)

(4)

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

(5)

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

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

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

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

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

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

(6)

則該網(wǎng)絡(luò)組網(wǎng)結(jié)構(gòu)一級通信關(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)一級通信關(guān)系單位功耗產(chǎn)生的成本是Pc1，二級通信關(guān)系單位功耗產(chǎn)生的成本是Pc2。則組網(wǎng)結(jié)構(gòu)總計成本為：

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

(9)

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

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

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

Dh>Dr>Dz

(10)

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

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

在進行路由節(jié)點部署時，對于一個節(jié)點，其所無線通信節(jié)點數(shù)是k，則：

對于一個匯聚節(jié)點，與其通信的節(jié)點數(shù)量如下：

0

(11)

對于一個路由節(jié)點，與其通信的節(jié)點數(shù)量如下：

0

(12)

對于一個終端節(jié)點，與其通信的節(jié)點數(shù)量如下：

kz=1

(13)

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

1.4 路由節(jié)點部署通信質(zhì)量評價模型

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

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

L=20lg(d+dL)

(14)

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

2 算法設(shè)計

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

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

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

2.1.1 HPSO設(shè)計

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

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

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

(15)

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

HPSO粒子更新表達式如下：

(16)

(17)

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

2.1.2 HPSO淘汰機制

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

(18)

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

(19)

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

2.1.3 HPSO多樣性補充機制

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

K=N·w

(20)

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

2.2 ADS算法設(shè)計

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

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

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

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

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

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

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

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

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

可視域范圍如下式：

(21)

x2+y2+z2

(22)

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

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

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

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

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

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

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

啟發(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é)點到下一節(jié)點的距離，Q(i,j,k)代表下一節(jié)點到目標(biāo)節(jié)點間的距離，S(i,j,k)計算式如下：

(24)

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

(25)

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

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

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

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

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

表1 算法參數(shù)

3.2 結(jié)果與分析

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

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

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

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

圖8 通信距離變化過程圖

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

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

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

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

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

表2 3種方法實驗結(jié)果

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

4 結(jié)束語

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

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