即時(shí)通信網(wǎng)絡(luò)中路由節(jié)點(diǎn)覆蓋控制優(yōu)化方法

安華萍，李龍亮

(1.河源職業(yè)技術(shù)學(xué)院 電子與信息工程學(xué)院，廣東 河源 517000；2.華為技術(shù)有限公司，廣東 深圳 518129)

路由器屬于無(wú)線傳感器網(wǎng)絡(luò)中的一部分，由眾多網(wǎng)絡(luò)節(jié)點(diǎn)組成，通過(guò)這些路由節(jié)點(diǎn)，即可部署出一個(gè)即時(shí)通信網(wǎng)絡(luò)[1]，因此國(guó)內(nèi)外都在積極研究路由節(jié)點(diǎn).國(guó)外對(duì)路由節(jié)點(diǎn)研究已久，并在20世紀(jì)前就成立路由節(jié)點(diǎn)研究工作組，對(duì)路由節(jié)點(diǎn)進(jìn)行研究，并將路由節(jié)點(diǎn)應(yīng)用在軍事當(dāng)中，形成路由節(jié)點(diǎn)數(shù)，只能給軍事指揮中心發(fā)送探測(cè)信息和數(shù)據(jù)流，不具有路由節(jié)點(diǎn)間的相互通信能力.此后國(guó)外愈加重視路由節(jié)點(diǎn)，對(duì)路由節(jié)點(diǎn)的功能進(jìn)一步開發(fā)，提出路由項(xiàng)目，并在各大學(xué)成立路由研究小組，和公司一起研究開發(fā)，制定關(guān)于路由節(jié)點(diǎn)的重要計(jì)劃和戰(zhàn)略[2].與國(guó)外相比較，國(guó)內(nèi)對(duì)路由節(jié)點(diǎn)的研究較晚，在20世紀(jì)后，才成立路由節(jié)點(diǎn)研究小組并資助研究人員對(duì)路由節(jié)點(diǎn)的研究.在隨后的幾年內(nèi)，實(shí)現(xiàn)路由節(jié)點(diǎn)覆蓋檢測(cè)技術(shù)，并安裝在飛行器上，收集飛船飛行過(guò)程中的數(shù)據(jù)，研發(fā)路由的WSN節(jié)點(diǎn)感知模型，研究分析特定情況下的路由節(jié)點(diǎn)感知能力及其形成的網(wǎng)絡(luò)性能[3].在文獻(xiàn)[4]中，提出了基于三角形計(jì)算的路由節(jié)點(diǎn)覆蓋控制方法，這種方法在計(jì)算過(guò)程中，一旦網(wǎng)絡(luò)的最大感應(yīng)半徑大于網(wǎng)絡(luò)傳輸通信半徑時(shí)，網(wǎng)絡(luò)的連通性難以得到保證.在文獻(xiàn)[5]中，提出了基于遺傳算法的路由節(jié)點(diǎn)覆蓋控制方法，卻未曾考慮在實(shí)際感知中網(wǎng)絡(luò)所感知范圍是處于不規(guī)則狀態(tài)，而這種狀態(tài)會(huì)給路由節(jié)點(diǎn)覆蓋質(zhì)量帶來(lái)影響[4-5].因此研究即時(shí)通信網(wǎng)絡(luò)中路由節(jié)點(diǎn)覆蓋控制優(yōu)化方法具有一定的現(xiàn)實(shí)意義.

1 研究即時(shí)通信網(wǎng)絡(luò)中路由節(jié)點(diǎn)覆蓋控制優(yōu)化方法

1.1 分析路由節(jié)點(diǎn)信號(hào)傳播特性

路由在傳播信號(hào)過(guò)程中，所存在的障礙物可能會(huì)導(dǎo)致路由信號(hào)在傳播過(guò)程中產(chǎn)生不同程度的信號(hào)衰減，導(dǎo)致路由節(jié)點(diǎn)信號(hào)傳遞出現(xiàn)損耗，最終傳遞出的網(wǎng)絡(luò)信號(hào)出現(xiàn)縮短、不準(zhǔn)確等問(wèn)題，而不同的障礙物對(duì)路由節(jié)點(diǎn)信號(hào)所產(chǎn)生的信號(hào)反射、散射和衍射也存在區(qū)別[6].因此假設(shè)路由節(jié)點(diǎn)發(fā)射端信號(hào)，在傳遞信息過(guò)程中所發(fā)生的與距離相關(guān)的損耗稱為路徑損耗，且在接收路由信號(hào)的過(guò)程中，接收信號(hào)的一端與發(fā)射信號(hào)的一端距離越遠(yuǎn)，所產(chǎn)生的路徑損耗越大，并且在這一過(guò)程中，呈現(xiàn)出對(duì)數(shù)衰減變化[7].所以設(shè)接收信號(hào)端與發(fā)射信號(hào)端的距離為d，路由節(jié)點(diǎn)成功接收到的信號(hào)功率(dBm)為P(d)，路由節(jié)點(diǎn)的最大傳輸距離為d0，路由信號(hào)節(jié)點(diǎn)在d時(shí)，信號(hào)發(fā)送功率為P0，則有：

(1)

式中，η為路由節(jié)點(diǎn)傳遞信號(hào)路徑損耗系數(shù)；X0為零均值的高斯分布隨機(jī)變量.根據(jù)式(1)，即可得到路由節(jié)點(diǎn)傳送信號(hào)的最大距離，以及在信號(hào)傳送過(guò)程中產(chǎn)生的損耗，從而確定路由節(jié)點(diǎn)的位置，將路由節(jié)點(diǎn)覆蓋在通信網(wǎng)絡(luò)中[8].

1.2 確定路由節(jié)點(diǎn)位置

1.2.1 部署錨節(jié)點(diǎn)

將即時(shí)通信網(wǎng)絡(luò)劃分成大小均等的區(qū)域，并在這個(gè)區(qū)域當(dāng)中，設(shè)定一個(gè)通信閾值[9].與此同時(shí)，將路由節(jié)點(diǎn)的通信范圍限制在一定的區(qū)域內(nèi)，降低路由節(jié)點(diǎn)的通信量，從而避免路由節(jié)點(diǎn)通信損耗，如圖1所示.

圖1 錨節(jié)點(diǎn)部署

圖1中，“o”表示錨節(jié)點(diǎn)，“*”表示位置節(jié)點(diǎn).根據(jù)上述即時(shí)通信網(wǎng)絡(luò)劃分內(nèi)容，將即時(shí)通信網(wǎng)絡(luò)看成如圖1所示的“10×10”網(wǎng)格，并按照?qǐng)D中的虛線，將網(wǎng)格劃分成4個(gè)大區(qū)域，按照實(shí)線，將網(wǎng)格劃分成100個(gè)小區(qū)域.根據(jù)區(qū)域位置，在每個(gè)大區(qū)域內(nèi)，布置一個(gè)錨節(jié)點(diǎn)，其他未知節(jié)點(diǎn)“*”是通過(guò)飛機(jī)間隔每幾秒進(jìn)行空投位置節(jié)點(diǎn)，從而得到圖1中的錨節(jié)點(diǎn)部署圖，根據(jù)預(yù)設(shè)的錨節(jié)點(diǎn)部署圖，即可計(jì)算路由節(jié)點(diǎn)最優(yōu)距離[10].

1.2.2 計(jì)算路由節(jié)點(diǎn)最優(yōu)距離

將圖1中的錨節(jié)點(diǎn)部署圖放置在二維空間當(dāng)中，采用三邊測(cè)量法，計(jì)算路由節(jié)點(diǎn)之間的距離[11],如圖2所示.

圖2 三邊測(cè)量計(jì)算圖

圖2中，U(x,y)表示未知節(jié)點(diǎn),B1(x1,y1)、B2(x2,y2)、B3(x3,y3)表示3個(gè)錨節(jié)點(diǎn)，當(dāng)3個(gè)錨節(jié)點(diǎn)B1(x1,y1)、B2(x2,y2)、B3(x3,y3)到未知節(jié)點(diǎn)U(x,y)的距離分別為圖2中的d1、d2、d3時(shí)，則有：

(2)

將(2)式轉(zhuǎn)換成位置矩陣，計(jì)算未知節(jié)點(diǎn)U(x,y)，則有：

(3)

1.3 路由節(jié)點(diǎn)覆蓋

1.3.1 評(píng)估路由節(jié)點(diǎn)覆蓋性能

在確定路由節(jié)點(diǎn)距離后，還需評(píng)估路由節(jié)點(diǎn)覆蓋性能，才可以在即時(shí)通信網(wǎng)絡(luò)覆蓋路由節(jié)點(diǎn)，從而計(jì)算路由節(jié)點(diǎn)的覆蓋率和覆蓋密度[13].當(dāng)即時(shí)通信網(wǎng)絡(luò)中所布置的路由節(jié)點(diǎn)稀疏時(shí)，設(shè)即時(shí)通信網(wǎng)絡(luò)實(shí)際覆蓋總面積為B，待覆蓋總面積為C，則有：

(4)

式中，A表示路由節(jié)點(diǎn)覆蓋率.此時(shí)還需計(jì)算路由節(jié)點(diǎn)的覆蓋密度，即時(shí)通信網(wǎng)絡(luò)區(qū)域中的任意一點(diǎn)K，都能被k個(gè)路由器節(jié)點(diǎn)所感知，此時(shí)的k表示路由節(jié)點(diǎn)覆蓋度的值，且k≥1[14].當(dāng)路由節(jié)點(diǎn)完全覆蓋即時(shí)通信網(wǎng)絡(luò)時(shí)，需要計(jì)算路由節(jié)點(diǎn)在即時(shí)網(wǎng)絡(luò)覆蓋中的連通性，確保路由節(jié)點(diǎn)之間具有通信能力.

1.3.2 計(jì)算路由節(jié)點(diǎn)覆蓋連通性

在路由節(jié)點(diǎn)全面覆蓋后，只有路由節(jié)點(diǎn)之間具有良好的連通性才能完成即時(shí)通信網(wǎng)絡(luò)所具有的基本功能[15].因此需要計(jì)算此時(shí)路由節(jié)點(diǎn)覆蓋后的連通性，是否符合即時(shí)通信網(wǎng)絡(luò)的需求.然而由文獻(xiàn)[16]可知，路由節(jié)點(diǎn)數(shù)量的增加會(huì)增加網(wǎng)絡(luò)的連通概率，所以，在計(jì)算路由節(jié)點(diǎn)覆蓋連通性之前，假設(shè)即時(shí)通信網(wǎng)絡(luò)初時(shí)僅有一個(gè)孤立的路由節(jié)點(diǎn)，當(dāng)不斷增加節(jié)點(diǎn)通信半徑時(shí)，節(jié)點(diǎn)的通信鏈路數(shù)量也會(huì)隨之增加[16].基于式(4)，對(duì)路由節(jié)點(diǎn)覆蓋率計(jì)算式可知，當(dāng)路由節(jié)點(diǎn)滿足其覆蓋最小節(jié)點(diǎn)度k時(shí)，此時(shí)路由節(jié)點(diǎn)會(huì)覆蓋在即時(shí)通信網(wǎng)絡(luò)中，形成一個(gè)k度網(wǎng)絡(luò)連通圖，且當(dāng)移走任意一個(gè)路由k-1節(jié)點(diǎn)后，即時(shí)通信網(wǎng)絡(luò)依然會(huì)處于連通狀態(tài)，不會(huì)影響即時(shí)通信網(wǎng)絡(luò)信息的傳遞，此時(shí)也可將即時(shí)通信網(wǎng)絡(luò)稱為k度網(wǎng)絡(luò)連通圖[17].因此設(shè)即時(shí)通信網(wǎng)絡(luò)為G，最小節(jié)點(diǎn)度為bmin，路由所有節(jié)點(diǎn)為P，路由所有節(jié)點(diǎn)的覆蓋面積為C，則有：

P(C)=P[bmin(C)>0]，

(5)

當(dāng)式(5)成立時(shí)，路由節(jié)點(diǎn)即可全面覆蓋在即時(shí)通信網(wǎng)絡(luò)中.當(dāng)式(5)中的P[bmin(C)>0]具有實(shí)際意義，且無(wú)限趨近于1時(shí)，可以得到路由節(jié)點(diǎn)之間連通率的極限值[18].則有：

(6)

式(6)中，n為常數(shù)；p為路由所有節(jié)點(diǎn)中的一個(gè)，即p∈P；AP為路由節(jié)點(diǎn)p的有效通信面積.此時(shí)將式(5)和式(6)聯(lián)立，則有：

(7)

式(7)中，?p∈G為任意一路由節(jié)點(diǎn)p，均屬于即時(shí)通信網(wǎng)絡(luò)G.此時(shí)則有：

P(C)=P[bmin(C)>0]=(1-e-nAP/Ω)，

(8)

當(dāng)式(8)成立時(shí)，得到的P(C)即是覆蓋在即時(shí)通信網(wǎng)絡(luò)上路由節(jié)點(diǎn)的有效連通率.綜上所述，即可優(yōu)化路由節(jié)點(diǎn)覆蓋控制.

1.4 路由節(jié)點(diǎn)覆蓋控制優(yōu)化

由圖1中給出的錨節(jié)點(diǎn)部署方式，將即時(shí)通信網(wǎng)絡(luò)中部署的路由節(jié)點(diǎn)構(gòu)成一個(gè)S集合，且在集合S中，所有路由節(jié)點(diǎn)的有效覆蓋面積為E(C)，當(dāng)即時(shí)通信網(wǎng)絡(luò)處于極端環(huán)境下，所部署的路由節(jié)點(diǎn)集合為空時(shí)，則有：

(9)

此時(shí)即可根據(jù)式(9)，得到即時(shí)通信網(wǎng)絡(luò)在部署路由節(jié)點(diǎn)不為空時(shí)的網(wǎng)絡(luò)覆蓋率，則有：

(10)

根據(jù)式(10)，可以看出在即時(shí)通信網(wǎng)絡(luò)中，覆蓋路由節(jié)點(diǎn)時(shí)，并不是所有路由節(jié)點(diǎn)都可以發(fā)揮出自身感知，存在路由節(jié)點(diǎn)覆蓋浪費(fèi)現(xiàn)象，形成如圖3所示的即時(shí)通信網(wǎng)絡(luò)覆蓋圖[19].

圖3 即時(shí)通信網(wǎng)絡(luò)覆蓋圖

從圖3中可以看出，路由節(jié)點(diǎn)覆蓋在即時(shí)通信網(wǎng)絡(luò)中，可以將即時(shí)通信網(wǎng)絡(luò)分為區(qū)域Ⅰ和區(qū)域Ⅱ，即內(nèi)區(qū)域和外區(qū)域兩部分.路由節(jié)點(diǎn)覆蓋在區(qū)域Ⅰ和區(qū)域Ⅱ上，會(huì)形成感應(yīng)圓周，與圓周的邊界交點(diǎn)分別為A和B，D點(diǎn)為路由節(jié)點(diǎn)p到區(qū)域Ⅱ的交點(diǎn)，C點(diǎn)為路由節(jié)點(diǎn)p到區(qū)域Ⅱ外的一點(diǎn)，為此時(shí)部署路由所有節(jié)點(diǎn)P，且節(jié)點(diǎn)P的感知半徑為rs，會(huì)出現(xiàn)圖3所示位置，則有：

E(C)=P(ΩΙ)E(CΩΙ)+P(ΩⅡ)E(CΩⅡ)，

(11)

式(11)中，P(ΩΙ)為節(jié)點(diǎn)P在區(qū)域Ⅰ的概率值；P(ΩⅡ)為節(jié)點(diǎn)P在區(qū)域Ⅱ的概率值；E(CΩΙ) 為節(jié)點(diǎn)P在區(qū)域Ⅰ的覆蓋期望值；E(CΩⅡ)為節(jié)點(diǎn)P在區(qū)域Ⅱ的覆蓋期望值.因此可以將式(11)中的節(jié)點(diǎn)P分為兩種情況，分別計(jì)算節(jié)點(diǎn)P在區(qū)域Ⅰ和區(qū)域Ⅱ覆蓋面積，則有：

(12)

此時(shí)可根據(jù)圖3，計(jì)算路由節(jié)點(diǎn)p在即時(shí)通信網(wǎng)絡(luò)中的感知區(qū)域，則有：

(13)

此時(shí)將式(11)和式(13)，則有：

(14)

經(jīng)(14)式計(jì)算，得到的E(C)即為路由節(jié)點(diǎn)在即時(shí)通信網(wǎng)絡(luò)中最優(yōu)覆蓋控制區(qū)域.此時(shí)路由節(jié)點(diǎn)覆蓋后，控制路由節(jié)點(diǎn)時(shí)所需能量最少，布置的路由節(jié)點(diǎn)最少，且屬于路由節(jié)點(diǎn)最大限度的感知范圍，既保證了即時(shí)通信網(wǎng)絡(luò)中的即時(shí)通信能力，還降低了路由節(jié)點(diǎn)的控制范圍[20].

2 實(shí)驗(yàn)論證分析

為了驗(yàn)證此次研究的路由節(jié)點(diǎn)覆蓋控制方法，設(shè)置的網(wǎng)絡(luò)和路由節(jié)點(diǎn)參數(shù)如表1所示.

表1 網(wǎng)絡(luò)和路由節(jié)點(diǎn)參數(shù)

在如表1所示的參數(shù)下，將此次研究的路由節(jié)點(diǎn)覆蓋控制方法作為實(shí)驗(yàn)A組，引言里提到的兩種路由節(jié)點(diǎn)覆蓋控制方法，分別作為實(shí)驗(yàn)B組和實(shí)驗(yàn)C組.基于路由節(jié)點(diǎn)覆蓋控制特點(diǎn)，分別從不同的網(wǎng)絡(luò)規(guī)模和目標(biāo)區(qū)域覆蓋度環(huán)境下活躍節(jié)點(diǎn)數(shù)量和網(wǎng)絡(luò)剩余能量?jī)煞矫?，分?組檢測(cè)方法，檢測(cè)對(duì)比活躍節(jié)點(diǎn)數(shù)量高低和網(wǎng)絡(luò)剩余能量多少.為了保證實(shí)驗(yàn)測(cè)試結(jié)果的可靠性和真實(shí)性，進(jìn)行50次實(shí)驗(yàn)，并將所得活躍節(jié)點(diǎn)數(shù)量和網(wǎng)絡(luò)剩余能量按實(shí)驗(yàn)次序繪成圖表，直觀上比較不同檢測(cè)方法的差異.

2.1 第1組實(shí)驗(yàn)

在如表1所示的條件下，改變網(wǎng)絡(luò)覆蓋度，分別使用3種方法覆蓋網(wǎng)絡(luò)，在路由節(jié)點(diǎn)覆蓋網(wǎng)絡(luò)后檢測(cè)路由節(jié)點(diǎn)中活躍節(jié)點(diǎn)數(shù)量，其實(shí)驗(yàn)結(jié)果如圖4所示.

網(wǎng)絡(luò)覆蓋度/%圖4 不同網(wǎng)絡(luò)覆蓋度下路由節(jié)點(diǎn)活躍數(shù)量

從圖4中可以看出，隨著網(wǎng)絡(luò)覆蓋度的增加，路由節(jié)點(diǎn)活躍數(shù)量也在不斷增加，但是實(shí)驗(yàn)A組的路由節(jié)點(diǎn)活躍數(shù)量，明顯高于實(shí)驗(yàn)B組和實(shí)驗(yàn)C組.此時(shí)將圖4中的實(shí)驗(yàn)數(shù)據(jù)統(tǒng)計(jì)成表，進(jìn)一步對(duì)比3組方法在不同網(wǎng)絡(luò)覆蓋度下路由節(jié)點(diǎn)的活躍數(shù)量，其統(tǒng)計(jì)結(jié)果如表2所示.

表2 數(shù)據(jù)統(tǒng)計(jì)表

從表2中可以看出，實(shí)驗(yàn)B組在網(wǎng)絡(luò)覆蓋度增加后，路由節(jié)點(diǎn)的活躍數(shù)量，平均值和方差都低于其他兩種實(shí)驗(yàn)方法，而實(shí)驗(yàn)A組在同一參數(shù)下，路由節(jié)點(diǎn)的活躍數(shù)量，平均值和方差遠(yuǎn)高于其他兩組實(shí)驗(yàn)方法.第1組實(shí)驗(yàn)結(jié)果表明，此次研究的路由節(jié)點(diǎn)覆蓋控制優(yōu)化方法，在覆蓋網(wǎng)絡(luò)后路由節(jié)點(diǎn)的活躍度相對(duì)較高，可以及時(shí)傳送數(shù)據(jù).

2.2 第2組實(shí)驗(yàn)

為進(jìn)一步驗(yàn)證此次研究的路由節(jié)點(diǎn)覆蓋控制優(yōu)化方法，在第1組實(shí)驗(yàn)的基礎(chǔ)上，進(jìn)行第2組實(shí)驗(yàn).在表1所示的參數(shù)下，將網(wǎng)絡(luò)的覆蓋度定為50%，對(duì)比3種方法覆蓋控制網(wǎng)絡(luò)后，網(wǎng)絡(luò)剩余能量隨時(shí)間的變化，實(shí)驗(yàn)結(jié)果如圖5所示.

時(shí)間/s圖5 網(wǎng)絡(luò)剩余能量隨時(shí)間的變化

從圖5中可以看出，實(shí)驗(yàn)B組和C組，在網(wǎng)絡(luò)覆蓋度為50%時(shí)，隨著運(yùn)行時(shí)間的增長(zhǎng)，運(yùn)行能量減少的十分迅速，分別在4 000 s和5 000 s就用盡路由節(jié)點(diǎn)所有能量；而實(shí)驗(yàn)A組在初始和結(jié)束時(shí)，路由節(jié)點(diǎn)運(yùn)行能量消耗較少，在運(yùn)行的過(guò)程中，一直處于勻速消耗狀態(tài)，在6 000 s運(yùn)行結(jié)束時(shí)，還參與5J.由此可見，此次研究的路由節(jié)點(diǎn)覆蓋控制優(yōu)化方法，提高了路由節(jié)點(diǎn)能量利用.綜合上述實(shí)驗(yàn)結(jié)果可知，此次研究的路由節(jié)點(diǎn)覆蓋控制優(yōu)化方法，增加了路由節(jié)點(diǎn)活躍數(shù)量，提高了路由節(jié)點(diǎn)的利用率.

3 結(jié) 論

綜上所述，此次研究路由節(jié)點(diǎn)覆蓋控制優(yōu)化方法，根據(jù)路由節(jié)點(diǎn)的性能、信號(hào)傳播距離等，在網(wǎng)絡(luò)中覆蓋路由節(jié)點(diǎn)，主要從路由節(jié)點(diǎn)傳播特點(diǎn)、節(jié)點(diǎn)之間的最優(yōu)距離、在網(wǎng)絡(luò)中的覆蓋和網(wǎng)絡(luò)中的覆蓋控制4方面入手.

(1)計(jì)算路由節(jié)點(diǎn)信號(hào)傳播距離在不同距離間產(chǎn)生的損耗；

(2)均勻布置錨節(jié)點(diǎn)，根據(jù)錨節(jié)點(diǎn)位置，計(jì)算路由節(jié)點(diǎn)位置確定路由節(jié)點(diǎn)距離；

(3)計(jì)算路由節(jié)點(diǎn)覆蓋率，確定網(wǎng)絡(luò)中覆蓋的路由節(jié)點(diǎn)具有連通性；

(4)控制網(wǎng)絡(luò)中覆蓋的路由節(jié)點(diǎn)，降低網(wǎng)絡(luò)運(yùn)行能耗.

通過(guò)此次研究取得了理論性研究成果，但是在研究過(guò)程中，發(fā)現(xiàn)網(wǎng)絡(luò)在覆蓋路由節(jié)點(diǎn)時(shí)，存在節(jié)點(diǎn)信號(hào)衰減、磁場(chǎng)噪聲干擾等問(wèn)題，導(dǎo)致路由節(jié)點(diǎn)在信號(hào)感知方面表現(xiàn)出一定程度的不確定性.因此在今后需要從路由節(jié)點(diǎn)動(dòng)態(tài)感知、外界干擾因素、路由節(jié)點(diǎn)的運(yùn)動(dòng)方式、多維空間的路由節(jié)點(diǎn)覆蓋等方面，深入研究路由節(jié)點(diǎn)在網(wǎng)絡(luò)中的覆蓋方法，提高網(wǎng)絡(luò)的服務(wù)質(zhì)量.