一種高覆蓋率和安全性的動(dòng)態(tài)傳感器網(wǎng)絡(luò)部署策略?

徐友洪 童根樹(shù)

(1.衢州職業(yè)技術(shù)學(xué)院信息工程學(xué)院，浙江 衢州 324000；2.浙江大學(xué)建筑工程學(xué)院，浙江 杭州 310058)

低成本集成和小型微型傳感器在可任意處理的傳感區(qū)域引起了極大的關(guān)注[1－4]。這些傳感器是可移動(dòng)的、隨機(jī)部署的、所需基礎(chǔ)設(shè)施較少且以數(shù)據(jù)為中心的傳感器，它們配備無(wú)法充電(或很少充電)或不可替換的數(shù)據(jù)處理器和感知電路，因此在能量、帶寬、存儲(chǔ)和處理能力方面受到限制；盡管如此，這些傳感器在國(guó)土安全、災(zāi)難后恢復(fù)、目標(biāo)識(shí)別、偵察、醫(yī)療應(yīng)用、防御應(yīng)用和入侵檢測(cè)等領(lǐng)域得到了廣泛應(yīng)用[5－6]，各個(gè)傳感器處理感測(cè)數(shù)據(jù)并以安全的方式傳送到目標(biāo)接收器。移動(dòng)性通過(guò)重定位這些傳感器并幫助建立從源到接收器的非冗余安全數(shù)據(jù)傳輸?shù)墓?jié)能路由來(lái)降低通信開(kāi)銷(xiāo)，從而最大化電池和傳感器的壽命；盡管移動(dòng)性和安全路由已在Ad-hoc 網(wǎng)絡(luò)中得到了廣泛的研究，但對(duì)于資源受限的移動(dòng)傳感器網(wǎng)絡(luò)仍是一個(gè)有待探索的領(lǐng)域。移動(dòng)傳感器網(wǎng)絡(luò)由隨機(jī)部署的可任意處理的傳感器構(gòu)成，它們彼此協(xié)作，使得覆蓋范圍和電池壽命最大化。在部署時(shí)，傳感器可以通過(guò)隨機(jī)游走擴(kuò)散到環(huán)境中。近年來(lái)，有不少學(xué)者提出了與移動(dòng)傳感器網(wǎng)絡(luò)研究有關(guān)的動(dòng)態(tài)方法。文獻(xiàn)[7]主要考慮傳感器節(jié)點(diǎn)一次部署一個(gè)，每個(gè)節(jié)點(diǎn)利用從先前部署的節(jié)點(diǎn)收集到的數(shù)據(jù)來(lái)確定其最佳部署位置；文獻(xiàn)[8]在文獻(xiàn)[7]的基礎(chǔ)上，提出了減少部署時(shí)間的潛在區(qū)域，進(jìn)一步提高了部署的效率；文獻(xiàn)[9]提出了傳感器節(jié)點(diǎn)對(duì)多個(gè)動(dòng)態(tài)變化環(huán)境的覆蓋響應(yīng)的自組織策略和算法；文獻(xiàn)[10]提出了一種基于優(yōu)化采樣的蒙特卡羅盒定位算法。該算法在釆樣階段引入了節(jié)點(diǎn)的接收信號(hào)強(qiáng)度信息用于進(jìn)一步縮小釆樣箱，使得從中獲取的初始樣本以更大的概率靠近待定位節(jié)點(diǎn)的實(shí)際位置，從而將傳感器最佳地部署到關(guān)鍵區(qū)域，以確保所需讀數(shù)的質(zhì)量；文獻(xiàn)[11]提出了與傳感器安全相關(guān)的研究，包括采用簡(jiǎn)單對(duì)稱(chēng)密碼算法和非對(duì)稱(chēng)密碼算法的解決方案，但由于傳感器節(jié)點(diǎn)上可用的計(jì)算、功率和存儲(chǔ)資源有限，所以非對(duì)稱(chēng)密碼算法不適合為無(wú)線傳感器網(wǎng)絡(luò)提供安全性；文獻(xiàn)[12]分析了拜占庭容錯(cuò)問(wèn)題的解決方案，通過(guò)對(duì)無(wú)線傳感器網(wǎng)絡(luò)中拜占庭容錯(cuò)問(wèn)題的技術(shù)難點(diǎn)分析，提出了一種基于快速ECDSAE 的輕量級(jí)拜占庭容錯(cuò)路由方案ELBFT。ELBFT 方案采用基于分簇的雙層拓?fù)洌槍?duì)不同的網(wǎng)絡(luò)層面執(zhí)行不同輪數(shù)的拜占庭容錯(cuò)，減少了簇間通信輪數(shù)，降低了網(wǎng)絡(luò)總通信量，有效地平衡了網(wǎng)絡(luò)負(fù)載；文獻(xiàn)[13－14]盡管提出了基于遺傳算法的能量平衡消耗和最大化連接覆蓋集，但它們僅用于實(shí)現(xiàn)靜態(tài)傳感器網(wǎng)絡(luò)的2 個(gè)目標(biāo)，即簇成員和到接收器的路由。

盡管上述大多數(shù)方案都是有用的，但側(cè)重于靜態(tài)傳感器網(wǎng)絡(luò)的覆蓋范圍最大化，同時(shí)盡量減少靜態(tài)傳感器網(wǎng)絡(luò)中的電池使用，它們無(wú)法全面處理移動(dòng)傳感器網(wǎng)絡(luò)中需要優(yōu)化競(jìng)爭(zhēng)的4 個(gè)主要目標(biāo):簇群、路由、定位和安全性，以獲得高能效的移動(dòng)傳感器網(wǎng)絡(luò)。對(duì)此，本文提出了一種遺傳算法，將隨機(jī)部署的移動(dòng)傳感器劃分和放置到一個(gè)具有簇頭和最佳路由的獨(dú)立簇的最優(yōu)數(shù)目中，簇頭從其成員傳感器收集數(shù)據(jù)，并通過(guò)最具成本效益的路由以壓縮和安全的方式將收集到的數(shù)據(jù)發(fā)送到接收器。一旦部署完畢，通過(guò)移動(dòng)(或重定位)自身來(lái)進(jìn)一步最大化它們的覆蓋范圍。總的來(lái)說(shuō)，傳感器網(wǎng)絡(luò)依賴(lài)于連續(xù)的隨機(jī)運(yùn)動(dòng)，通過(guò)安全性、簇頭最短路徑和負(fù)荷遷移等，使節(jié)點(diǎn)處于最佳接觸狀態(tài)。實(shí)驗(yàn)結(jié)果表明，相比于靜態(tài)部署，本文提出的動(dòng)態(tài)部署不僅提高了傳感器的覆蓋率，而且在保證安全性的同時(shí)降低了節(jié)點(diǎn)丟失百分比。

1 問(wèn)題模型

1.1 遺傳算法

遺傳算法(genetic algorithm，GA)是模擬自然進(jìn)化的一種隨機(jī)搜索技術(shù)，已成功應(yīng)用于廣泛的組合問(wèn)題中，也是計(jì)算科學(xué)人工智能領(lǐng)域中用于解決最優(yōu)化的一種搜索啟發(fā)式算法，是進(jìn)化算法的一種；遺傳算法在適應(yīng)度函數(shù)選擇不當(dāng)?shù)那闆r下有可能收斂于局部最優(yōu)，而不能達(dá)到全局最優(yōu)。遺傳算法的基本運(yùn)算過(guò)程如下:

(1)初始化:設(shè)置進(jìn)化代數(shù)計(jì)數(shù)器t＝0，設(shè)置最大進(jìn)化代數(shù)T，隨機(jī)生成M個(gè)個(gè)體作為初始種群體P(0)；

(2)個(gè)體評(píng)價(jià):計(jì)算種群P(t)中各個(gè)個(gè)體的適應(yīng)度；

(3)選擇運(yùn)算:將選擇算子作用于種群。選擇的目的是把優(yōu)化的個(gè)體直接遺傳到下一代或通過(guò)配對(duì)交叉產(chǎn)生新的個(gè)體再遺傳到下一代。選擇操作是建立在種群中個(gè)體的適應(yīng)度評(píng)價(jià)的基礎(chǔ)上；

(4)交叉運(yùn)算:將交叉算子作用于種群。遺傳算法中起核心作用的就是交叉算子；

(5)變異運(yùn)算:將變異算子作用于種群。即對(duì)種群中的個(gè)體串的某些基因座上的基因值作變動(dòng)。種群P(t)經(jīng)過(guò)選擇、交叉、變異運(yùn)算之后得到下一代種群體P(t＋1)；

(6)終止條件判斷:若t＝T，則以進(jìn)化過(guò)程中所得到的具有最大適應(yīng)度個(gè)體作為最優(yōu)解輸出，終止計(jì)算。

GA 在涉及設(shè)計(jì)和優(yōu)化的應(yīng)用中特別有用，在這些應(yīng)用中存在大量的變量，并且過(guò)程算法要么不存在，要么非常復(fù)雜；簡(jiǎn)單的GA 收斂于單一解。

1.2 基于遺傳算法的靜態(tài)傳感器適應(yīng)度

對(duì)于靜態(tài)傳感器來(lái)說(shuō)，每個(gè)單獨(dú)的傳感器節(jié)點(diǎn)都采用遺傳算法分配一個(gè)職能分工。這些功能表示為:(1)不活動(dòng)節(jié)點(diǎn)(即供電中斷)；(2)簇頭(Cluster Head，CH)；(3)簇間路由器(Inter-Cluster Router，ICR)和(4)傳感器節(jié)點(diǎn)(Sensor Node，NS)。每個(gè)簇用一個(gè)簇頭來(lái)表示，簇成員用不活動(dòng)/活動(dòng)節(jié)點(diǎn)傳感器和ICR 來(lái)表示。簇頭負(fù)責(zé)來(lái)自于各個(gè)節(jié)點(diǎn)傳感器的數(shù)據(jù)融合，簇間路由器負(fù)責(zé)將簇?cái)?shù)據(jù)(來(lái)自于簇頭)傳送到接收器。對(duì)于采用遺傳算法的靜態(tài)傳感器網(wǎng)絡(luò)來(lái)說(shuō)，通常定義如下適應(yīng)度參數(shù):

(1)覆蓋適應(yīng)度(Coverage Fitness，CF):最優(yōu)化總的覆蓋范圍，目標(biāo)是最大化總的檢測(cè)區(qū)域；

(2)簇頭適應(yīng)度(Cluster-Head Fitness，CHF):基于傳感器節(jié)點(diǎn)和簇頭的均勻性定義的適應(yīng)度；

(3)節(jié)點(diǎn)通信適應(yīng)度(Node Communication Fitness，NCF):定義與簇頭通信所需的功率，可以采用路徑損耗來(lái)進(jìn)行計(jì)算；

(4)電池狀態(tài)適應(yīng)度(Battery Status Fitness，BSF):用于最優(yōu)化節(jié)點(diǎn)分配定義的閾值，即電池狀態(tài)/使用情況；

(5)路由器負(fù)荷適應(yīng)度(Router Load Fitness，RLF):如果路由器(ICR)連接了超過(guò)簇頭的平均數(shù)量，它就對(duì)路由器(ICR)進(jìn)行懲罰，以避免ICR過(guò)載；

(6)傳感器執(zhí)行器適應(yīng)度(Sensor Effector Fitness，SEF):它給出簇傳感器執(zhí)行所消耗的能量。SEF的有效效應(yīng)是對(duì)傳感器節(jié)點(diǎn)進(jìn)行重新部署，以使得通過(guò)融合、刪除或壓縮等方法對(duì)傳感器數(shù)據(jù)傳輸進(jìn)行均勻優(yōu)化；

(7)總節(jié)點(diǎn)適應(yīng)度(Total Node Fitness，TNF):對(duì)于合適的節(jié)點(diǎn)分配來(lái)說(shuō)，TNF計(jì)算如下:

式中:α1＋α2＋α3＋α4＋α5＋α6＝1，αi依賴(lài)于各適應(yīng)度的相對(duì)重要性，這些值可以用外部啟發(fā)式方法進(jìn)行調(diào)整；

(8) 路由選擇適應(yīng)度函數(shù)(Route Selection Fitness Function，RSFF):它采用基于節(jié)點(diǎn)適應(yīng)度函數(shù)的GA 的節(jié)點(diǎn)分配生成均衡的路由。在建立過(guò)程中，CH和ICR 在成本效益最高的路由器上開(kāi)始發(fā)送數(shù)據(jù)。

2 移動(dòng)傳感器網(wǎng)絡(luò)的遺傳算法

2.1 移動(dòng)性擴(kuò)展

這部分將討論基于GA 的移動(dòng)性，目標(biāo)是實(shí)現(xiàn)節(jié)能動(dòng)態(tài)部署。

移動(dòng)性允許節(jié)點(diǎn)進(jìn)行功率優(yōu)化，請(qǐng)求其他節(jié)點(diǎn)進(jìn)行數(shù)據(jù)融合來(lái)執(zhí)行協(xié)作感知和進(jìn)行修正，并定位要報(bào)告的數(shù)據(jù)。但移動(dòng)性隨著移動(dòng)要付出代價(jià)，可以通過(guò)傳感器節(jié)點(diǎn)監(jiān)測(cè)自身功率的能力，以及傳感器節(jié)點(diǎn)與環(huán)境動(dòng)態(tài)的相互作用來(lái)實(shí)現(xiàn)一種最佳的移動(dòng)策略，通過(guò)重新部署節(jié)點(diǎn)的位置，就可利用移動(dòng)性來(lái)最大化適應(yīng)度，從而獲得以下定義的適應(yīng)度參數(shù)的優(yōu)化。

2.1.1 覆蓋均勻性適應(yīng)度

覆蓋均勻性適應(yīng)度(Coverage Uniformity Fitness，CUF)通過(guò)利用傳感器的移動(dòng)來(lái)填充覆蓋孔和最大化檢測(cè)區(qū)域，以實(shí)現(xiàn)覆蓋范圍的改善，是通過(guò)再平衡簇成員節(jié)點(diǎn)之間的通信距離來(lái)實(shí)現(xiàn)的。位置較近的節(jié)點(diǎn)因移動(dòng)而得到獎(jiǎng)勵(lì)，而更遠(yuǎn)的節(jié)點(diǎn)因?yàn)檫_(dá)到覆蓋均衡而相互移動(dòng)也得到獎(jiǎng)勵(lì)。當(dāng)節(jié)點(diǎn)間距離達(dá)到最優(yōu)時(shí)，與相鄰節(jié)點(diǎn)的距離和所需的傳輸功率最小化，這有助于最大化NCF。CUF計(jì)算如下:

式中:M為簇?cái)?shù)目，dj＿min和dj＿mean分別為簇j中節(jié)點(diǎn)間的最小通信距離和平均通信距離，ej＿min和ej＿mean分別為簇j中各個(gè)節(jié)點(diǎn)與簇頭之間的最小通信距離和平均通信距離。

顯然，均勻分布的傳感器節(jié)點(diǎn)比采用不規(guī)則拓?fù)涞墓?jié)點(diǎn)消耗的能量更均勻，GA 通過(guò)對(duì)傳感器的定位方式來(lái)增強(qiáng)傳感器的移動(dòng)能力，以增大覆蓋范圍，減少節(jié)點(diǎn)間的干擾，最大限度地減少通信所需的功率。

2.1.2 簇－節(jié)點(diǎn)遷移適應(yīng)度

簇－節(jié)點(diǎn)遷移適應(yīng)度(Cluster-Node Migration Fitness，CNMF)通過(guò)獎(jiǎng)勵(lì)傳感器節(jié)點(diǎn)具有低CHF簇頭之間的傳感器節(jié)點(diǎn)的遷移來(lái)提高傳感器節(jié)點(diǎn)和簇頭的均勻性。如果傳感器遷移是從高密度簇遷移到低密度簇，則遷移有助于獲得更高的CHF。CNMF計(jì)算如下:

式中:n是第n個(gè)遷移對(duì)(源－目標(biāo)簇)，N是遷移對(duì)的總數(shù)目，χns是過(guò)多的傳感器節(jié)點(diǎn)的源簇度量，χnt是傳感器節(jié)點(diǎn)的耗盡數(shù)量的目標(biāo)簇度量，ρn是附著在這個(gè)簇頭上的節(jié)點(diǎn)數(shù)，ρ是系統(tǒng)中每個(gè)簇的平均節(jié)點(diǎn)數(shù)，計(jì)算為:

當(dāng)傳感器節(jié)點(diǎn)位于源簇和目標(biāo)簇間擴(kuò)散梯度較高的低CHF簇中時(shí)，適應(yīng)度表達(dá)式對(duì)傳感器節(jié)點(diǎn)的遷移有一定的獎(jiǎng)勵(lì)。

2.1.3 簇頭遷移適應(yīng)度

簇頭遷移適應(yīng)度(Cluster-Head Migration Fitness，CHMF)獎(jiǎng)勵(lì)具有較低路由器負(fù)荷適應(yīng)度的簇頭和簇間路由器的移動(dòng)。CH 和ICR 的移動(dòng)可以有助于獲得更高的RLF，原因如下:

(1)ICR 或CH 移動(dòng)可以基于各種因素改變ICR 的成員。這樣可以?xún)?yōu)化連接到移動(dòng)的ICR 上的CH/ICR 的數(shù)目；

(2)ICR 還可以移動(dòng)與另一個(gè)功能節(jié)點(diǎn)(簇頭、傳感器節(jié)點(diǎn))交換角色。這可以通過(guò)為路由器目標(biāo)交換具有較高電池容量的節(jié)點(diǎn)來(lái)幫助維護(hù)現(xiàn)有的拓?fù)浣Y(jié)構(gòu)。CHMF計(jì)算如下:

式中:N是移動(dòng)節(jié)點(diǎn)的總數(shù)目，RLFn是第n個(gè)節(jié)點(diǎn)的路由器負(fù)荷適應(yīng)度(見(jiàn)1.1)，BFnt是與具有BFns的第n個(gè)ICR 節(jié)點(diǎn)交換的非ICR 節(jié)點(diǎn)的電池適應(yīng)度，ηn是表示第n個(gè)ICR 的交換對(duì)的布爾值。

從式(5)可以看出，傳感器在具有較低的電池和路由器負(fù)荷適應(yīng)度的ICR 和CH 上移動(dòng)會(huì)得到獎(jiǎng)勵(lì)，節(jié)點(diǎn)移動(dòng)通過(guò)再平衡影響路由器的負(fù)荷，通過(guò)交換功能目標(biāo)影響電池的容量。

2.1.4 節(jié)點(diǎn)運(yùn)動(dòng)適應(yīng)度

節(jié)點(diǎn)運(yùn)動(dòng)適應(yīng)度(Node Motion Fitness，NMF)表明一個(gè)節(jié)點(diǎn)的平均行程與它的運(yùn)動(dòng)有關(guān)，但以電池壽命為代價(jià)。因此，期望距離是對(duì)能量供給有限的節(jié)點(diǎn)所需能量的估計(jì)。因此，希望在達(dá)到總體系統(tǒng)目標(biāo)(覆蓋范圍和延長(zhǎng)網(wǎng)絡(luò)壽命)的同時(shí)，穩(wěn)定運(yùn)動(dòng)特性。這些特性與運(yùn)動(dòng)頻率和振蕩有關(guān)。

(1)運(yùn)動(dòng)頻率度量傳感器在一個(gè)閾值限定的給定時(shí)間內(nèi)的平均運(yùn)動(dòng)，閾值是由電池適應(yīng)度定義的電池壽命的函數(shù)。具有有限電池壽命的傳感器的較大運(yùn)動(dòng)會(huì)受到懲罰，這使得隨著系統(tǒng)的老化，實(shí)現(xiàn)運(yùn)動(dòng)的能力受到很大的抑制；

(2)位置穩(wěn)定性度量由于競(jìng)爭(zhēng)目標(biāo)節(jié)點(diǎn)無(wú)法達(dá)到穩(wěn)定的位置，節(jié)點(diǎn)因過(guò)度運(yùn)動(dòng)或非持續(xù)振蕩而受到懲罰。

NMF計(jì)算如下:

式中:?i(n)(0≤?i(n)≤1)是第i個(gè)傳感器節(jié)點(diǎn)在n次訪問(wèn)同一位置時(shí)的懲罰，F(xiàn)i(·)是第i個(gè)傳感器節(jié)點(diǎn)的懲罰，且0≤Fi(Q，節(jié)點(diǎn)類(lèi)型)≤1，Q是量化步驟中表示的電池狀態(tài)，d是節(jié)點(diǎn)移動(dòng)的估計(jì)距離，它通過(guò)在不同的已知傳感器位置上讀取多個(gè)能量，并采用基于能量的定位來(lái)間接估計(jì)。

第i個(gè)傳感器在時(shí)間間隔t上測(cè)得的信號(hào)能量以yi(t)表示，計(jì)算為:

式中:Gi是第i個(gè)傳感器的增益因子，α(≈2)為能量衰減因子，εi(t)是參數(shù)建模誤差的累積效應(yīng)，S(t)表示目標(biāo)在時(shí)間t發(fā)射的能量，r(t)(D×1)表示目標(biāo)在時(shí)刻t的坐標(biāo)向量，ri(D×1)表示第i個(gè)穩(wěn)定傳感器的笛卡爾坐標(biāo)向量。

2.1.5 傳感器數(shù)據(jù)適應(yīng)度

傳感器數(shù)據(jù)適應(yīng)度(Sensor Data Fitness，SDF)用重新定位傳感器節(jié)點(diǎn)的凈效應(yīng)來(lái)度量傳感器的數(shù)據(jù)效率，使得其數(shù)據(jù)傳輸通過(guò)融合、刪除或壓縮方法被均勻地優(yōu)化。在資源受限中的最優(yōu)感知用θ(B，F(xiàn))表示，其中B是與傳感操作相關(guān)的服務(wù)質(zhì)量要求，F(xiàn)是計(jì)時(shí)器策略。實(shí)現(xiàn)服務(wù)質(zhì)量特性是為了利用可變的數(shù)據(jù)壓縮和融合規(guī)則，根據(jù)傳感器的條件(如傳感器密度)執(zhí)行計(jì)時(shí)器以改變比特率。傳感器的運(yùn)動(dòng)可以通過(guò)以下方式減少簇中的平均能量需求而得到獎(jiǎng)勵(lì):

(1)由于最近移動(dòng)的傳感器分擔(dān)負(fù)荷，減少了計(jì)時(shí)器活動(dòng)的變動(dòng)；

(2)由于最近移動(dòng)的傳感器觸發(fā)了新的融合規(guī)則，并且由于冗余傳感器的移動(dòng)消除了冗余感知，因此減少了比特?cái)?shù)。

在給定的信噪比下，獎(jiǎng)勵(lì)過(guò)程的凈結(jié)果是最佳傳感器密度和每秒的比特?cái)?shù)。SDF計(jì)算如下:

式中:λ1＋λ2＝1，F(xiàn)＝{F1，F(xiàn)2，…，F(xiàn)N}和B＝{B1，B2，…，BN}分別表示簇n的每個(gè)傳感器節(jié)點(diǎn)的平均頻率和比特率，簇n中傳感器節(jié)點(diǎn)已經(jīng)被檢測(cè)到，ψ(X，n)表示傳感器參數(shù)X的改善增益，X用其在簇n中的連續(xù)抽樣實(shí)例之間的平均值()和方差()的變化來(lái)表示，λ1和λ2可以基于傳感器實(shí)現(xiàn)來(lái)調(diào)整。

與節(jié)點(diǎn)運(yùn)動(dòng)相關(guān)聯(lián)的總適應(yīng)度由總的節(jié)點(diǎn)運(yùn)動(dòng)適應(yīng)度確定如下:

式中:α1＋α2＋α3＋α4＋α5＝1，且單個(gè)權(quán)值依賴(lài)于實(shí)現(xiàn)。

2.2 節(jié)點(diǎn)部署的遺傳算法實(shí)現(xiàn)

根據(jù)TNMF，就可以采用GA 算子設(shè)計(jì)出最佳節(jié)點(diǎn)部署算法。在接收器中執(zhí)行GA，在多個(gè)觸發(fā)器上重復(fù)。這些觸發(fā)器與電池報(bào)警、惡化的路由適應(yīng)度報(bào)警和周期性操作有關(guān)。一旦達(dá)到最佳適應(yīng)度，與最佳適應(yīng)度相對(duì)應(yīng)的部署就被提交，并指示傳感器放棄舊的位置來(lái)獲取新的位置。

2.2.1 染色體表示

GA 的染色體是以適合于遺傳算子和適應(yīng)度函數(shù)的形式來(lái)解決問(wèn)題的構(gòu)建模塊。染色體串由每個(gè)傳感器節(jié)點(diǎn)的運(yùn)動(dòng)向量構(gòu)成，運(yùn)動(dòng)向量用一個(gè)名為“gene”的7 位二進(jìn)制數(shù)表示，如圖1 所示，在本例中，節(jié)點(diǎn)1、2 進(jìn)行3 次替換，節(jié)點(diǎn)3、4 進(jìn)行2 次替換，節(jié)點(diǎn)5、6、9 只替換1 次，其他節(jié)點(diǎn)不移動(dòng)。染色體串層次定義為:

圖1 基于GA 算法的節(jié)點(diǎn)重定位

(1)()表示0°(00)，90°(01)，180°(10)、270°(11)的角運(yùn)動(dòng)；

(3)只有當(dāng)x值之一為1 時(shí)，才會(huì)移動(dòng)傳感器。

2.2.2 初始種群

初始染色體串采用隨機(jī)數(shù)發(fā)生器(random number generator，RNG)部分隨機(jī)生成，且部分采用先前樣本的種群。

2.2.3 評(píng)價(jià)

每個(gè)染色體串采用由式(9)定義的TNMF函數(shù)(用于節(jié)點(diǎn)部署)進(jìn)行適應(yīng)度評(píng)價(jià)。

2.2.4 繁殖

繁殖允許適應(yīng)度較高的個(gè)體(串)對(duì)下一代中的后代有更高概率的貢獻(xiàn)。由于TNMF定義了適應(yīng)度值，所以具有最高TNMF值的染色體有更好的機(jī)會(huì)參與繁殖。算法采用標(biāo)準(zhǔn)加權(quán)輪盤(pán)法選擇n個(gè)個(gè)體到采用交叉概率生成N個(gè)染色體的交配池中。在繁殖過(guò)程中，選擇多個(gè)交叉點(diǎn)，其位置采用RNG 計(jì)算。

2.2.5 突變

復(fù)制的N個(gè)染色體被轉(zhuǎn)移到突變池中，突變池中的突變算子根據(jù)自適應(yīng)變異概率對(duì)它們進(jìn)行突變，自適應(yīng)變異概率與平均適應(yīng)度成反比:

式中:pm為最大變異概率，突變采用函數(shù)翻轉(zhuǎn)來(lái)決定是否反轉(zhuǎn)比特。

2.2.6 選擇

最后，根據(jù)適應(yīng)度值從N＋n(n個(gè)父本和N個(gè)孩子)中選擇n個(gè)染色體，并遺傳給下一代。

2.3 安全性擴(kuò)展

至止，已經(jīng)采用GA 算法并行執(zhí)行前3 個(gè)傳感器目標(biāo)簇群、路由和定位。這三個(gè)目標(biāo)的可靠運(yùn)行依賴(lài)于各個(gè)功能單元之間的安全通信，這就需要識(shí)別已損壞或錯(cuò)誤添加的節(jié)點(diǎn)、安全重新部署/添加節(jié)點(diǎn)和防止惡意入侵者采用身份認(rèn)證、完整性、隱私以及反回放等因素進(jìn)行被動(dòng)監(jiān)聽(tīng)，即全部通信都必須是安全的，以避免入侵者截獲、分析和更改數(shù)據(jù)，從而降低傳感器網(wǎng)絡(luò)的有效性。

在本文的安全模型中，把接收器視為是一個(gè)可信的組件，它為不同節(jié)點(diǎn)類(lèi)型之間的數(shù)據(jù)安全轉(zhuǎn)發(fā)建立必要的信任關(guān)系。最靠近接收器的節(jié)點(diǎn)構(gòu)成最受信任的關(guān)系，也就是說(shuō)，節(jié)點(diǎn)從接收器開(kāi)始構(gòu)建信任層次，這從預(yù)先確定的路由決策中可以看出，預(yù)先確定的路由決策是在建立期間和稍后重新配置期間創(chuàng)建的。由于與命令/消息執(zhí)行、數(shù)據(jù)轉(zhuǎn)發(fā)等相關(guān)的原因，安全體系結(jié)構(gòu)的要素在不同的節(jié)點(diǎn)類(lèi)型之間建立信任關(guān)系。任何身份認(rèn)證都是通過(guò)可信路由層次結(jié)構(gòu)的接收器和組件來(lái)實(shí)現(xiàn)的。為了實(shí)現(xiàn)高效的身份認(rèn)證，本文采用安全網(wǎng)絡(luò)加密協(xié)議(secure network encryption protocol，SNEP)[15]的某些要素。協(xié)議的加密部分在第一發(fā)起者(first-initiator，F(xiàn)I)和接收器之間執(zhí)行，層次結(jié)構(gòu)中的其他組件充當(dāng)身份認(rèn)證(或非身份認(rèn)證)的通過(guò)。第一發(fā)起者可以是一個(gè)簇頭或一個(gè)ICR，它們要么發(fā)起命令，要么參與數(shù)據(jù)融合，以便將數(shù)據(jù)傳送到接收器。這些安全要素包括:

(1)主密鑰(Master Key，MK)得到對(duì)稱(chēng)加密(Kencr)和消息認(rèn)證(Kauth)密鑰，并生成偽隨機(jī)數(shù)(Krand)。得到的密鑰可基于接收器的請(qǐng)求隨機(jī)更改，主密鑰在節(jié)點(diǎn)和接收器之間先驗(yàn)地共享，并用于專(zhuān)門(mén)的節(jié)點(diǎn)－接收器傳遞消息。采用得到的密鑰Krand和一個(gè)計(jì)數(shù)器C來(lái)生成偽隨機(jī)數(shù)。這個(gè)偽隨機(jī)數(shù)在加密之前被插入到消息中，以避免純文本攻擊。

(2)節(jié)點(diǎn)間通信密鑰(inter-node communication key，INCK)是兩個(gè)節(jié)點(diǎn)之間由接收器主導(dǎo)的共享密鑰，用于對(duì)它們之間的消息進(jìn)行認(rèn)證(INCKmac)。由于接收器知道路由層次結(jié)構(gòu)，所以它為參與認(rèn)證的每個(gè)ICR(或CH)封裝。每個(gè)節(jié)點(diǎn)采用其Kencr(從主密鑰得到)解密封裝的數(shù)據(jù)包并提取其INCK。是分別用于端口0 和端口1 的MAC 密鑰。

(3)這里采用反模式分組密碼[15]進(jìn)行加密/解密，采用CBC-MAC[16]作為身份認(rèn)證。反模式分組密碼要求在節(jié)點(diǎn)和接收器之間共享計(jì)數(shù)器，由于它是一個(gè)流密碼，消息長(zhǎng)度與純文本相同，因此通信開(kāi)銷(xiāo)較低。雖然一些路由器可以用作傳遞，但其他路由器則采用基于MAC 的身份認(rèn)證來(lái)執(zhí)行準(zhǔn)入控制。接收器可以改變ICR 和CH 的認(rèn)證要求，這依賴(lài)于能量需求和通過(guò)電池量化級(jí)和壞數(shù)據(jù)包數(shù)量來(lái)測(cè)得的安全威脅級(jí)別，同時(shí)通過(guò)標(biāo)識(shí)重要節(jié)點(diǎn)來(lái)維護(hù)足夠的安全級(jí)別。重要節(jié)點(diǎn)通過(guò)評(píng)估電池狀態(tài)、網(wǎng)絡(luò)流量、特定路由上的格式錯(cuò)誤或重試以及單個(gè)路由處理身份認(rèn)證中的節(jié)點(diǎn)數(shù)來(lái)優(yōu)化啟用安全性。為此，下面定義一個(gè)適應(yīng)度函數(shù)，該適應(yīng)度函數(shù)是競(jìng)爭(zhēng)傳感器節(jié)點(diǎn)上安全要素的最佳啟用。

2.3.1 安全節(jié)點(diǎn)適應(yīng)度

安全節(jié)點(diǎn)適應(yīng)度(secure node fitness，SNF)基于感知到的涉及數(shù)據(jù)完整性的威脅來(lái)獎(jiǎng)勵(lì)在節(jié)點(diǎn)上啟用的安全性。接收器跟蹤在特定路由上接收到的全部格式錯(cuò)誤的數(shù)據(jù)包。盡管路由(CH→接收器)因攜帶格式錯(cuò)誤和重試的數(shù)據(jù)包而受到懲罰，但它們因啟用路由器(ICR)上的身份認(rèn)證和簇頭上的加密而受到獎(jiǎng)勵(lì)。如果啟用了與量化為M級(jí)的威脅級(jí)別不成比例的身份認(rèn)證，則給予附加懲罰。SNF獎(jiǎng)勵(lì)根據(jù)電池量化級(jí)別和電池使用率測(cè)得的安全屬性的節(jié)能啟用。接收器采用滯后性來(lái)計(jì)算表示數(shù)據(jù)通信、連接節(jié)點(diǎn)的平均數(shù)量和移動(dòng)等的電池使用量。SNF計(jì)算如下:

式中:λ1＋λ2＝1，λ2是第一發(fā)起者加密的獎(jiǎng)勵(lì)貢獻(xiàn)，R是路由總數(shù)目，θi是由接收器計(jì)算的路由i的威脅等級(jí)，Ki是路由i中啟用身份認(rèn)證和加密節(jié)點(diǎn)ICR 和CH 的數(shù)目，N是路由i中節(jié)點(diǎn)ICR 和CH 的總數(shù)目，如果路由i中的節(jié)點(diǎn)n被啟用作為身份認(rèn)證，則＝1，否則為0，(·)是在路由j上啟用對(duì)節(jié)點(diǎn)i的接納控制的懲罰，Q是節(jié)點(diǎn)i的電池電平，ψ是電池使用率。

2.3.2 啟用安全性的遺傳算法

本節(jié)設(shè)計(jì)在節(jié)點(diǎn)上啟用安全屬性(加密和身份認(rèn)證)的遺傳算法。把這些節(jié)點(diǎn)用一個(gè)染色體串來(lái)表示，染色體串采用每個(gè)傳感器節(jié)點(diǎn)的安全策略構(gòu)成，安全策略由一個(gè)2 位二進(jìn)制數(shù)表示，定義為:

式中:(e1a1a2…aN)i表示路由i的節(jié)點(diǎn)n上的安全屬性(en＆an)，en和an分別表示加密比特和認(rèn)證比特。注意，第一個(gè)節(jié)點(diǎn)總是一個(gè)CH 節(jié)點(diǎn)，其中的數(shù)據(jù)加密可以通過(guò)設(shè)置en＝1 來(lái)任意進(jìn)行。遺傳算法的步驟類(lèi)似于1.2 的步驟。

安全設(shè)置與節(jié)點(diǎn)選擇或移動(dòng)相競(jìng)爭(zhēng)。節(jié)點(diǎn)是基于相應(yīng)的適應(yīng)度因子分配功能或位置的，這些適應(yīng)度因子由于電池條件對(duì)于確保數(shù)據(jù)包安全來(lái)說(shuō)可能是次優(yōu)的。這將觸發(fā)重新配置，直至所有目標(biāo)達(dá)到可接受的收斂為止，就像節(jié)點(diǎn)/路由選擇和移動(dòng)性估計(jì)一樣，這是在系統(tǒng)生命周期內(nèi)重復(fù)的一個(gè)動(dòng)態(tài)過(guò)程，如圖2 所示。

圖2 接收器在ICR 和CH 端口主導(dǎo)INCK 密鑰

這些密鑰支持基于遺傳算法生成的安全屬性染色體的認(rèn)證。例如，節(jié)點(diǎn)2 不需要端口0 的消息認(rèn)證，而是需要端口1 的消息認(rèn)證。。

2.4 算法計(jì)算復(fù)雜度分析

在考慮安全性擴(kuò)展的情況下，算法實(shí)現(xiàn)主要包括2 個(gè)階段。一是移動(dòng)傳感器網(wǎng)絡(luò)實(shí)現(xiàn)本身的GA算法，二是在安全性擴(kuò)展下的安全節(jié)點(diǎn)適應(yīng)度計(jì)算和安全性啟用2 個(gè)過(guò)程；對(duì)于第一個(gè)階段，對(duì)于移動(dòng)節(jié)點(diǎn)總數(shù)目為N的傳感器網(wǎng)絡(luò)來(lái)說(shuō)，如果進(jìn)化代數(shù)為T(mén)，初始種群為M，則通過(guò)選擇運(yùn)算、交叉運(yùn)算和變異運(yùn)算，算法執(zhí)行的時(shí)間復(fù)雜度分別為N「M/T?、MT和M，一般情況下，N很大于T和M，所以這個(gè)階段的計(jì)算復(fù)雜度為N「M/T?(其中「·?表示向下取整)；對(duì)于第二個(gè)階段，其中的安全節(jié)點(diǎn)適應(yīng)度計(jì)算會(huì)增加N個(gè)節(jié)點(diǎn)的身份認(rèn)證和加密計(jì)算，即增加N次加法運(yùn)算，在GA 算法中啟用安全性時(shí)由于要用2位二進(jìn)制數(shù)來(lái)表示安全策略，總共要進(jìn)行2N次乘法計(jì)算；所以結(jié)合第一階段的計(jì)算復(fù)雜度，整個(gè)算法實(shí)現(xiàn)的計(jì)算復(fù)雜度為N「M/T?＋2N。

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

實(shí)驗(yàn)設(shè)置由在一個(gè)30×30(歸一化單位長(zhǎng)度)空間內(nèi)隨機(jī)位置上的100 個(gè)節(jié)點(diǎn)構(gòu)成，各個(gè)節(jié)點(diǎn)在(0，0)～(30，30)之間獲取一個(gè)隨機(jī)坐標(biāo)，并分配它們自己一個(gè)通用唯一識(shí)別碼和0～15 之間的隨機(jī)電池容量。為簡(jiǎn)單起見(jiàn)，給每個(gè)節(jié)點(diǎn)3×3(歸一化單位長(zhǎng)度)的覆蓋區(qū)域，一旦全部節(jié)點(diǎn)進(jìn)入偵聽(tīng)模式，遺傳算法將以60%的交叉率和6%的初始突變率運(yùn)行。假設(shè)傳感器節(jié)點(diǎn)之間為視距傳播，實(shí)現(xiàn)的遺傳算法軟件仿真器與網(wǎng)絡(luò)仿真器NS－2 一起運(yùn)行，NS－2 軟件用于仿真網(wǎng)絡(luò)流量。軟件仿真器執(zhí)行GA 生成運(yùn)動(dòng)路徑和安全屬性，并根據(jù)網(wǎng)絡(luò)流量、電池使用情況和接收數(shù)據(jù)包的完整性計(jì)算所定義的適應(yīng)度參數(shù)；仿真器中的獨(dú)立進(jìn)程運(yùn)行一個(gè)預(yù)測(cè)算法，預(yù)測(cè)算法采用過(guò)去的滯后性來(lái)估計(jì)未來(lái)的流量和數(shù)據(jù)完整性，并將這些數(shù)據(jù)用于估計(jì)GA 運(yùn)行中的適應(yīng)度參數(shù)；當(dāng)每個(gè)GA 目標(biāo)趨向于與其他目標(biāo)競(jìng)爭(zhēng)收斂到系統(tǒng)均衡時(shí)，最終的結(jié)果就使得網(wǎng)絡(luò)壽命最大化，以獲得最佳覆蓋。

圖3 所示為靜態(tài)和動(dòng)態(tài)部署時(shí)覆蓋率與進(jìn)化代的數(shù)量的關(guān)系?？梢钥吹?，由于運(yùn)動(dòng)而實(shí)現(xiàn)的動(dòng)態(tài)部署，使得覆蓋率比靜態(tài)部署平均提高了約30%。當(dāng)然，移動(dòng)也伴隨著通信開(kāi)銷(xiāo)，這是由于運(yùn)動(dòng)指令的加密和認(rèn)證以及觸發(fā)通信路由上增強(qiáng)的認(rèn)證屬性的節(jié)點(diǎn)移動(dòng)而導(dǎo)致臨時(shí)數(shù)據(jù)包丟失和數(shù)據(jù)損壞。盡管移動(dòng)會(huì)增加電池消耗，但可通過(guò)節(jié)點(diǎn)重新部署降低通信成本來(lái)補(bǔ)償。

圖3 靜態(tài)和動(dòng)態(tài)部署時(shí)覆蓋率與進(jìn)化代數(shù)量的關(guān)系

圖4 所示為節(jié)點(diǎn)丟失百分比與進(jìn)化代數(shù)量的關(guān)系。可以看到，動(dòng)態(tài)部署明顯優(yōu)于靜態(tài)部署，節(jié)點(diǎn)丟失百分比平均減少了約18%；還可看到，節(jié)點(diǎn)在靜態(tài)部署情況下呈指數(shù)級(jí)丟失，而在動(dòng)態(tài)部署情況下，由于總能量的更好分布，簇群中的節(jié)點(diǎn)是逐漸丟失的。靜態(tài)部署節(jié)點(diǎn)死亡導(dǎo)致的覆蓋損失會(huì)導(dǎo)致傳輸能量的增加和更長(zhǎng)的路由。本文算法在優(yōu)化節(jié)點(diǎn)分配的同時(shí)，還利用安全性和移動(dòng)性擴(kuò)展提高了傳感器網(wǎng)絡(luò)的覆蓋范圍、壽命和完整性；圖5 所示為安全性擴(kuò)展通過(guò)基于接收器感知的威脅級(jí)別動(dòng)態(tài)切換認(rèn)證和加密對(duì)遺傳算法的進(jìn)一步改進(jìn)。從圖4 可見(jiàn)，在第600 代和第700 代結(jié)束時(shí)，未考慮安全性擴(kuò)展的節(jié)點(diǎn)丟失百分比分別為40%和61%，而從圖5 可見(jiàn)，考慮安全性擴(kuò)展后在第600 代和第700 代結(jié)束時(shí)的節(jié)點(diǎn)丟失百分比平均分別為26%和44%，節(jié)點(diǎn)丟失百分比明顯下降；但還可看到，隨著進(jìn)化代數(shù)和威脅級(jí)別的增加，節(jié)點(diǎn)丟失百分比是增大的，這是由于安全節(jié)點(diǎn)(CH 和ICR)上的計(jì)算和報(bào)頭數(shù)據(jù)開(kāi)銷(xiāo)增加了，導(dǎo)致能量損失更大，從而增大了節(jié)點(diǎn)丟失百分比。

圖4 靜態(tài)和動(dòng)態(tài)部署時(shí)節(jié)點(diǎn)丟失百分比與進(jìn)化代數(shù)的關(guān)系

圖5 第500 代和第700 代結(jié)束時(shí)節(jié)點(diǎn)丟失百分比與威脅級(jí)別θi 的關(guān)系

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

本文提出了采用多目標(biāo)遺傳算法的移動(dòng)傳感器的動(dòng)態(tài)、安全和節(jié)能部署。算法通過(guò)利用移動(dòng)性重定位傳感器節(jié)點(diǎn)位置，進(jìn)一步優(yōu)化節(jié)點(diǎn)的分配、路由和安全屬性，從而最大限度地提高傳感器網(wǎng)絡(luò)的覆蓋范圍和壽命；此外，還提出了一種新的方法，使安全屬性與感知到的威脅級(jí)別成比例，并且能夠促進(jìn)電池的有效使用，將異常節(jié)點(diǎn)的影響降到最低；未來(lái)將研究從網(wǎng)絡(luò)中排除異常節(jié)點(diǎn)的能力，以及更好地描述網(wǎng)絡(luò)壽命中的能量分布。