李蘭英，蔣維成，何 勇，李華兵

(成都理工大學(xué) 工程技術(shù)學(xué)院，四川 樂(lè)山 614000)

0 引 言

無(wú)線傳感器常布置在野外，實(shí)現(xiàn)對(duì)某一任務(wù)的監(jiān)測(cè)，能量對(duì)無(wú)線傳感器網(wǎng)絡(luò)的運(yùn)行十分重要[1-4]。由于無(wú)線傳感器網(wǎng)絡(luò)在軍事、醫(yī)療、生產(chǎn)和生活中的重要作用，引起了廣泛的研究[5-7]。簇樹(shù)結(jié)構(gòu)是無(wú)線傳感網(wǎng)絡(luò)的一種常用網(wǎng)絡(luò)，文獻(xiàn)[8]設(shè)計(jì)不平衡的分簇，采用調(diào)度算法進(jìn)行傳輸任務(wù)的分配來(lái)保證傳輸時(shí)延滿足條件。文獻(xiàn)[9]采用自適應(yīng)信標(biāo)交換算法和基于過(guò)渡帶思想的貪婪轉(zhuǎn)發(fā)策略，提出了一種實(shí)時(shí)可靠的貪婪路由算法，提高了數(shù)據(jù)實(shí)時(shí)傳輸?shù)目煽啃?。這些文獻(xiàn)側(cè)重研究實(shí)時(shí)數(shù)據(jù)的延遲。

為了對(duì)無(wú)線傳感器網(wǎng)絡(luò)中的節(jié)點(diǎn)進(jìn)行管理，LEACH算法[10-12]采用分簇的方式，把無(wú)線傳感器網(wǎng)絡(luò)中的節(jié)點(diǎn)分為簇頭節(jié)點(diǎn)和普通成員節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)以一定的概率當(dāng)選為簇頭。簇頭負(fù)責(zé)數(shù)據(jù)的轉(zhuǎn)發(fā)和簇內(nèi)節(jié)點(diǎn)的管理，普通成員節(jié)點(diǎn)進(jìn)行數(shù)據(jù)的采集。由于簇頭能量消耗比較多，經(jīng)過(guò)一段時(shí)間要進(jìn)行簇頭輪換。然而LEACH算法的分簇是隨機(jī)進(jìn)行的，不足在于簇頭聚集在一起。

為了充分利用區(qū)域中無(wú)線傳感器節(jié)點(diǎn)能量，使得各節(jié)點(diǎn)能量的消耗均衡化，提出了一種能量均衡的地理位置監(jiān)測(cè)方法。

1 算法框架

文獻(xiàn)[13]指出無(wú)線傳感器在不同狀態(tài)下的能量消耗存在某種關(guān)系，在空閑狀態(tài)、數(shù)據(jù)接收和數(shù)據(jù)發(fā)送時(shí)的能量消耗是1∶1∶5。

為了研究無(wú)線傳感器網(wǎng)絡(luò)中各種不同狀態(tài)下任務(wù)量之間的關(guān)系，定義一個(gè)標(biāo)準(zhǔn)任務(wù)。

定義1：標(biāo)準(zhǔn)任務(wù)是對(duì)無(wú)線傳感器所執(zhí)行的眾多任務(wù)的抽象，用來(lái)衡量其他任務(wù)的任務(wù)量大小，用S0表示。

無(wú)線傳感器在執(zhí)行各種不同任務(wù)時(shí)可以通過(guò)標(biāo)準(zhǔn)任務(wù)量來(lái)衡量任務(wù)的大小。無(wú)線傳感器在執(zhí)行數(shù)據(jù)采集任務(wù)時(shí)的任務(wù)量可以表示為：S1=α·S0，其中α為比例系數(shù)，表示數(shù)據(jù)采集的任務(wù)量與標(biāo)準(zhǔn)任務(wù)之間的關(guān)系。無(wú)線傳感器在執(zhí)行接收數(shù)據(jù)任務(wù)時(shí)的任務(wù)量可以表示為：S2=β·S0，其中β為比例系數(shù)，表示接收數(shù)據(jù)的任務(wù)量與標(biāo)準(zhǔn)任務(wù)之間的關(guān)系。無(wú)線傳感器在執(zhí)行發(fā)送數(shù)據(jù)任務(wù)時(shí)的任務(wù)量可以表示為S3=γ·S0，其中γ為比例系數(shù)，表示發(fā)送數(shù)據(jù)的任務(wù)量與標(biāo)準(zhǔn)任務(wù)之間的關(guān)系。

定義2：能量窗口指無(wú)線傳感器的剩余能量與標(biāo)準(zhǔn)任務(wù)之間的乘積。

若能量窗口用W表示，則有：

W=E·S0

(1)

其中，E表示無(wú)線傳感器的剩余能量。

能量窗口反映無(wú)線傳感器節(jié)點(diǎn)在剩余時(shí)間里所能完成的任務(wù)量的多少。能量窗口越大，節(jié)點(diǎn)所能完成的任務(wù)量越多；反之，則越少。

無(wú)線傳感器在執(zhí)行一定的任務(wù)之后，就將能量窗口減少一定的量Δθ。如圖1所示，無(wú)線傳感器在執(zhí)行某任務(wù)之后，能量窗口由θ1變成θ2。

圖1 能量窗口

有了能量窗口之后，就可以清楚地知道區(qū)域內(nèi)各節(jié)點(diǎn)的能量窗口大小，在分配任務(wù)時(shí)就可以根據(jù)任務(wù)量的大小選擇不同的執(zhí)行節(jié)點(diǎn)，也可以?xún)?yōu)先把任務(wù)分配給能量窗口大的無(wú)線傳感器，這些無(wú)線傳感器可以完成更多的任務(wù)。

無(wú)線傳感器的監(jiān)測(cè)范圍是有限的。距離事發(fā)點(diǎn)位置越近的無(wú)線傳感器，監(jiān)測(cè)效果越佳。設(shè)事件發(fā)生位置的中心O坐標(biāo)為(x0,y0)，無(wú)線傳感器i的位置坐標(biāo)為(xi,yi)，那么無(wú)線傳感器i到O的距離為：

(2)

取距離的倒數(shù)F為:

(3)

其中，f0為監(jiān)測(cè)允許范圍的最小值。由式3可知，F(xiàn)的值越大，無(wú)線傳感器離事發(fā)中心的距離越近，監(jiān)測(cè)效果越好。

選取F和W作為參考量，構(gòu)建能距關(guān)系式，表示為：

(4)

其中，k1,k2為比例系數(shù)，表示F和W所占的比例。通過(guò)系數(shù)k1,k2在D和W之間進(jìn)行折衷和權(quán)衡來(lái)選擇區(qū)域中的無(wú)線傳感器作為任務(wù)的執(zhí)行節(jié)點(diǎn)，將滿足條件的無(wú)線傳感器構(gòu)成一個(gè)集合，把監(jiān)測(cè)的任務(wù)分擔(dān)給集合中的節(jié)點(diǎn)，來(lái)執(zhí)行監(jiān)測(cè)任務(wù)。使得任務(wù)監(jiān)測(cè)的能量消耗分散在區(qū)域中的不同節(jié)點(diǎn)之間。

由式4可知，在能量窗口相同的情況下，任務(wù)的執(zhí)行優(yōu)先選擇距離事發(fā)地點(diǎn)較近位置的無(wú)線傳感器，隨著任務(wù)監(jiān)測(cè)的進(jìn)行，節(jié)點(diǎn)的能量不斷消耗，使得G值減小，當(dāng)減少到一定量后，選擇其他節(jié)點(diǎn)來(lái)執(zhí)行任務(wù)。

如圖2所示，事件發(fā)生的中心位置位于O點(diǎn)，任務(wù)執(zhí)行節(jié)點(diǎn)首先選擇與O點(diǎn)較近的節(jié)點(diǎn)i，隨著能量的消耗，E值不斷減小，從而G值不斷減小，在O點(diǎn)附件存在比i點(diǎn)G值更大的無(wú)線傳感器j，從而使得j成為任務(wù)執(zhí)行節(jié)點(diǎn)，當(dāng)j的能量消耗到一定量后，又由k節(jié)點(diǎn)擔(dān)任任務(wù)的監(jiān)測(cè)。從而對(duì)O的監(jiān)測(cè)能耗分散在不同的節(jié)點(diǎn)之間，避免了節(jié)點(diǎn)提前死亡。

圖2 節(jié)點(diǎn)選擇

2 任務(wù)分配

2.1 分配樹(shù)

定義3：分配樹(shù)是由無(wú)線傳感器的F值和W值構(gòu)成的有序樹(shù)，用來(lái)對(duì)無(wú)線傳感器進(jìn)行任務(wù)分配。

在分配樹(shù)中，中間節(jié)點(diǎn)均是無(wú)線傳感器的G值，并且滿足如下性質(zhì)：第一，每個(gè)左子樹(shù)或者為空，或者左子樹(shù)上的所有節(jié)點(diǎn)小于它的父節(jié)點(diǎn)；第二，每個(gè)右子樹(shù)或者為空，或者不小于它的父節(jié)點(diǎn)。分配樹(shù)中所有的葉子節(jié)點(diǎn)均為無(wú)線傳感器的F值或W值，如果該葉子節(jié)點(diǎn)位于某子樹(shù)的左葉子位置，則為該無(wú)線傳感器的F值，位于右葉子位置則為該無(wú)線傳感器的W值。

如圖3所示，無(wú)線傳感器i1和i2的能量窗口W均為0.5，i1與事發(fā)中心的距離為50 m，其F值為0.02，G值為0.224；無(wú)線傳感器i2與事發(fā)中心的距離為14 m，其F值為0.07，G值為0.232；由于i2的G值比i1大，所以i1位于i2的左側(cè)。無(wú)線傳感器i3和i4與事發(fā)中心的距離均為10 m，F(xiàn)值為0.1，i3的能量窗口W為0.7，G值為0.326，i4的能量窗口W為0.8，G為0.369，由于i4的G值比i3大，所以i4位于i3的右側(cè)。

根據(jù)分配樹(shù)的性質(zhì)，任務(wù)的執(zhí)行可以選擇分配樹(shù)的右子樹(shù)所對(duì)應(yīng)的無(wú)線傳感器，因?yàn)橛易訕?shù)的G值更大。在圖3所示的分配樹(shù)中，優(yōu)先選擇右側(cè)的節(jié)點(diǎn)，可以選擇無(wú)線傳感器i4執(zhí)行任務(wù)。

圖3 分配樹(shù)

2.2 聚類(lèi)處理

為了使處理簡(jiǎn)單和減少執(zhí)行任務(wù)過(guò)程中節(jié)點(diǎn)的頻繁變換，若t1時(shí)刻的G值為G1，t2時(shí)刻的為G2，其中t2>t1。設(shè)置一個(gè)閾值h0，當(dāng)|G2-G1|≤h0時(shí)視為不變，只有當(dāng)|G2-G1|>h0時(shí)，才認(rèn)為發(fā)生改變，此刻進(jìn)行節(jié)點(diǎn)間的輪換。

由于區(qū)域中的無(wú)線傳感器數(shù)量比較多，考慮實(shí)際的G值之間的差異，將無(wú)線傳感器進(jìn)行聚類(lèi)處理，把G值相同的無(wú)線傳感器歸為一類(lèi)，這樣就可以簡(jiǎn)化操作。

根據(jù)區(qū)域中無(wú)線傳感器G值的分布情況進(jìn)行劃分。設(shè)Gn是某一類(lèi)G值中數(shù)量較多無(wú)線傳感器的中心值，那么可以根據(jù)式5計(jì)算屬于該類(lèi)的無(wú)線傳感器。

(5)

其中，ρ為閾值，表示無(wú)線傳感器允許偏離中心值Gn的范圍。根據(jù)式5可以將區(qū)域中的無(wú)線傳感器劃分成不同的類(lèi)，每一類(lèi)無(wú)線傳感器中的節(jié)點(diǎn)是等效的。在實(shí)際應(yīng)用中，可以根據(jù)具體情況，針對(duì)G值進(jìn)行不同的劃分。

對(duì)區(qū)域中的無(wú)線傳感器進(jìn)行聚類(lèi)處理之后，無(wú)線傳感器節(jié)點(diǎn)就屬于不同的集合，同一集合中的無(wú)線傳感器均是等效的，對(duì)于同一集合中的節(jié)點(diǎn)就可以按某種概率進(jìn)行選擇。若集合中有n個(gè)元素，那么選擇該集合中的某一無(wú)線傳感器節(jié)點(diǎn)i的概率為：

(6)

這樣就可以將任務(wù)分配給這n個(gè)節(jié)點(diǎn)。一方面將能量消耗分散在這n個(gè)節(jié)點(diǎn)之間，另外，由于這n個(gè)節(jié)點(diǎn)是等效的，也提高了系統(tǒng)的可靠性。

3 仿真結(jié)果

為了研究文中算法的性能，采用Matlab對(duì)文中算法和Leach算法構(gòu)建模型，進(jìn)行仿真實(shí)驗(yàn)。

從圖4可以看出，文中算法的死亡出現(xiàn)時(shí)間要比LEACH算法晚，在相同時(shí)間條件下，文中算法在無(wú)線傳感器死亡數(shù)量上也較LEACH算法少。這主要因?yàn)槲闹兴惴▽?shù)據(jù)監(jiān)測(cè)的任務(wù)分配給符合條件的無(wú)線傳感器節(jié)點(diǎn)集合，使得能量的消耗均衡化，減少了節(jié)點(diǎn)的過(guò)度能耗。

圖4 死亡數(shù)

任務(wù)的執(zhí)行是通過(guò)無(wú)線傳感器完成的，區(qū)域中一定數(shù)量的存活無(wú)線傳感器是保證任務(wù)的完成的前提[14]。在相同條件下，文中算法和LEACH算法中的節(jié)點(diǎn)存活數(shù)隨時(shí)間的變化如圖5所示。可以看出，在相同時(shí)間條件下，文中算法的節(jié)點(diǎn)存活數(shù)比LEACH算法要多，因而文中算法比LEACH算法有更長(zhǎng)的網(wǎng)絡(luò)生存期。

圖5 存活數(shù)

4 結(jié)束語(yǔ)

為了充分利用該無(wú)線傳感器的能量，提出了能量窗口的概念，在監(jiān)測(cè)效果允許范圍內(nèi)，構(gòu)建監(jiān)測(cè)距離和能量窗口關(guān)系式，在能量窗口和監(jiān)測(cè)距離之間進(jìn)行權(quán)衡選擇，把能量消耗分散在眾多等效無(wú)線傳感器節(jié)點(diǎn)之間。根據(jù)監(jiān)測(cè)距離和能量窗口構(gòu)建任務(wù)分配樹(shù)，實(shí)現(xiàn)對(duì)無(wú)線傳感器的快速指派，同時(shí)，根據(jù)無(wú)線傳感器節(jié)點(diǎn)的特性，將區(qū)域內(nèi)的無(wú)線傳感器進(jìn)行聚類(lèi)處理，把共同特性的無(wú)線傳感器歸為一類(lèi)，簡(jiǎn)化操作，提高算法的可靠性。最后，通過(guò)仿真實(shí)驗(yàn)驗(yàn)證了該算法的正確性。