孫澤宇，徐 琛，蘇艷超，李傳鋒，聶雅琳

1.洛陽理工學(xué)院 計算機與信息工程學(xué)院，河南 洛陽471023

2.上海應(yīng)用技術(shù)大學(xué) 計算機科學(xué)與信息工程學(xué)院，上海201418

3.河南省高技術(shù)創(chuàng)業(yè)服務(wù)中心 信息技術(shù)部，鄭州450008

傳感網(wǎng)中路由協(xié)議主要負責(zé)將數(shù)據(jù)報文按照路由鏈表某種指定路徑將數(shù)據(jù)報文從源節(jié)點發(fā)送至目的節(jié)點過程[1-3]。其研究主要問題可分為：（1）如何確定最優(yōu)化路徑，將數(shù)據(jù)報文從源節(jié)點發(fā)送至目的節(jié)點；（2）能量問題直接影響整個傳感網(wǎng)生存周期。對于一個魯棒性健壯的傳感網(wǎng)來說，能量有效可以以較長的時間來延長整個網(wǎng)絡(luò)。在數(shù)據(jù)傳遞過程中，傳感器節(jié)點在接收與轉(zhuǎn)發(fā)數(shù)據(jù)時均要消耗其本身能量[4-6]。因此，網(wǎng)絡(luò)能量不僅是傳感網(wǎng)中研究的重點課題，也是傳感網(wǎng)研究領(lǐng)域的熱點問題。

傳感網(wǎng)中傳統(tǒng)的路由協(xié)議是以感知層為主的底層路由協(xié)議。其缺點是，網(wǎng)絡(luò)中可控節(jié)點數(shù)量較少，對網(wǎng)絡(luò)資源配置與優(yōu)化計算能力較弱，算法復(fù)雜不易實現(xiàn)[7]。在數(shù)據(jù)傳輸過程往往采用犧牲節(jié)點能量為代價完成數(shù)據(jù)通信任務(wù)；數(shù)據(jù)在傳輸過程中跳數(shù)較多，對網(wǎng)絡(luò)動態(tài)變化反映速度較慢。與底層路由相比，傳感網(wǎng)中的分簇路由的特點如下：

（1）分簇路由可以提供更好的數(shù)據(jù)融合機制。簇內(nèi)節(jié)點相對集中部署在某一監(jiān)測區(qū)域內(nèi)，采集到的數(shù)據(jù)具有很高的相似性和冗余度，經(jīng)過簇首節(jié)點的數(shù)據(jù)融合操作，能夠得到較高的數(shù)據(jù)融合效果。通常情況下，簇成員節(jié)點總是直接將數(shù)據(jù)發(fā)送給簇首節(jié)點，減少了數(shù)據(jù)延時，提高了傳輸?shù)男省?/p>

（2）分簇網(wǎng)絡(luò)中，簇成員節(jié)點的功能相對簡單，無需維護復(fù)雜的路由信息。這樣，網(wǎng)絡(luò)中路由控制消息的開銷減小很多，節(jié)省了能量[8-9]。同時，簇成員節(jié)點在不工作的情況下，可以關(guān)閉發(fā)送和接收模塊，使之處于休眠狀態(tài)，也在很大程度上節(jié)省了能量的開銷。

（3）分簇結(jié)構(gòu)中，簇首節(jié)點充當(dāng)管理節(jié)點角色，便于管理網(wǎng)絡(luò)拓撲結(jié)構(gòu)，可以對整個系統(tǒng)變體做出快速反應(yīng)，具有較好的可擴展性，適用于大規(guī)模傳感網(wǎng)系統(tǒng)。

（4）分簇路由機制在一對多、多對一的通信中非常有效，分簇路由更容易克服由于傳感器節(jié)點加入、移動和失效帶來的網(wǎng)絡(luò)拓撲結(jié)構(gòu)變化問題。但是，由于傳感器節(jié)點自身體積較小，攜帶電量有限且無法充電，其通信能力、計算能力和存儲能力有限，導(dǎo)致分簇路由所執(zhí)行時間較長、錯誤性較高、數(shù)據(jù)融合效果不佳等原因。

本文借助于霧計算理論知識提出了A Cross-layersensing Cluster Routing Protocol Based on Fog Computer（CCRP）。該算法利用感知事件驅(qū)動機制將霧節(jié)點映射該算法通過跨層映射原理，利用感知事件驅(qū)動機制將霧節(jié)點映射到傳感層，將傳感網(wǎng)分簇路由協(xié)議的控制過程上傳至霧層，通過霧計算實現(xiàn)事件域節(jié)點分布式成簇路由匯聚中心。在路由協(xié)議優(yōu)化階段，本文借助于粒子群優(yōu)化算法（Particle Swarm Optimization，PSO）采用無競爭開銷方式選舉一組最佳節(jié)點擔(dān)任簇首，能有效地均衡全網(wǎng)能量的開銷，抑制傳感器節(jié)點能量的快速消耗，延長了網(wǎng)絡(luò)生存周期。

本文的主要貢獻主要集中在以下四點：

首先對相關(guān)工作進行了認真地分析，結(jié)合路由算法實現(xiàn)數(shù)據(jù)有效傳輸?shù)牟蛔?，本文給出了網(wǎng)絡(luò)模型。針對該模型提出了霧層分簇路由結(jié)構(gòu)，設(shè)定了邊界參考閾值，給出了跨層分簇網(wǎng)絡(luò)中通信節(jié)點的能耗計算模型。

為了更好地抑制節(jié)點能量消耗，本文引入了粒子群優(yōu)化（Particle Swarm Optimization，PSO）。由霧節(jié)點（Fog Node，F(xiàn)N）計算節(jié)點的平均能量，節(jié)點能量大于或等于平均能量的節(jié)點成為候選簇首節(jié)點，簇首節(jié)點在候選簇首中產(chǎn)生。讓每一個粒子代表一種可能的分簇方式，用目標(biāo)函數(shù)評價其性能，從中尋找最優(yōu)解，使目標(biāo)函數(shù)取得最小值。

基于上述兩點，本文以候選簇首為研究對象，縮減簇首節(jié)點的選擇范圍，通過能量順序鏈表確保候選節(jié)點具有較高能量。同時也給出了完成傳感網(wǎng)底層到霧層分簇路由的最優(yōu)簇的數(shù)量和單跳距離d1-hop=dopt+Δd的能耗增量小于單跳距離為d1-hop=dopt-Δd 能耗增量計算方法。

為了更好地驗證本文算法，本文給出了在不同時刻下節(jié)點狀態(tài)分布情況和不同參數(shù)下節(jié)點剩余能量以及網(wǎng)絡(luò)生存周期的對比過程，以驗證本文算法的有效性和穩(wěn)定性。

1 相關(guān)工作

網(wǎng)絡(luò)分簇包括簇的形成和簇頭選擇兩個方面，其關(guān)鍵問題是如何在節(jié)點剩余能量隨網(wǎng)絡(luò)運行時間不斷減少時，動態(tài)快速有產(chǎn)地尋找一組最佳節(jié)點擔(dān)任簇首節(jié)點，使形成的網(wǎng)絡(luò)分簇既能減少簇內(nèi)成員節(jié)點的能耗，又能使整個網(wǎng)絡(luò)能量消耗均衡。這是一個NP 難問題?；谥悄苋杭S機選擇的進化算法可以有效地解決上述問題，通過智能群集算法可以有效地避免陷入過早陷入最優(yōu)解，找到全局最優(yōu)解。

文獻[10]給出了一種基于分區(qū)能耗、均衡的非均勻分簇算法。其根本思想是，將傳感網(wǎng)進行分區(qū)，在距離匯聚節(jié)點較近的區(qū)域內(nèi)分簇數(shù)量較多，各簇內(nèi)成員節(jié)點數(shù)量相對較少；而遠離匯聚節(jié)點的分簇數(shù)量較少，各簇內(nèi)成員節(jié)點數(shù)量相對較多，從而保證承擔(dān)數(shù)據(jù)中繼轉(zhuǎn)發(fā)任務(wù)書的簇首能減少自身的簇內(nèi)通信開銷，以達到節(jié)省能量開銷的目的。文獻[11]提出了一種基于分簇的數(shù)據(jù)匯聚傳送協(xié)議。該協(xié)議通過均衡能耗的分簇方法及數(shù)據(jù)預(yù)測傳送機制，可以有效地抑制節(jié)點能量的快速消耗，從而達到延長網(wǎng)絡(luò)生存周期的目的。文獻[12]利用簇內(nèi)轉(zhuǎn)換傳輸機制給出傳感器節(jié)點在不同時間內(nèi)不同狀態(tài)轉(zhuǎn)換過程。通過傳感器節(jié)點不同的狀態(tài)特性，完成數(shù)據(jù)傳輸最優(yōu)路徑的選擇方法，最終完成數(shù)據(jù)在源節(jié)點與目的節(jié)點之間的傳輸。文獻[13]提出Distributed and Morphological Operation-based Data Collection Algorithm（DMOA）。該算法利用分簇網(wǎng)絡(luò)模型計算每個節(jié)點的鄰居具體位置信息，同時生成一個鄰居節(jié)點為中心監(jiān)測區(qū)域，并計算鄰居節(jié)點的剩余能量，將其按照權(quán)值的大小存儲在鏈表當(dāng)中。下一周期初始時刻，從鏈表中取得能量較高的節(jié)點作為簇首節(jié)點直至鏈表中所有節(jié)點的能量均小于閾值。文獻[14]給出了一種具有能量感知能力的分簇策略。該策略采用概率模型優(yōu)化選擇分簇方式，既能最小化簇內(nèi)距離，又能最優(yōu)化網(wǎng)絡(luò)能量。該策略采用的是輪回機制，每一輪包括兩個階段：即簇內(nèi)建立和穩(wěn)定階段。簇的建立階段采用集中控制策略，在基站完成，然后基站將分簇信息廣播至每個節(jié)點，簇內(nèi)和簇間路由均采用單跳方式。文獻[15]提了A Trust-Based Secure Routing（TBSR）算法。其基本思想是，利用概率模型，記錄路由鏈表中標(biāo)記下一節(jié)點所接收數(shù)據(jù)的動態(tài)轉(zhuǎn)換關(guān)系。當(dāng)任意節(jié)點受到攻擊或誤傳時，網(wǎng)絡(luò)將采用回溯的方法來定位和清除惡意節(jié)點，以確保安全。鏈表中所標(biāo)記的概率越高，則數(shù)據(jù)包在路由路徑上傳輸?shù)母怕示驮酱?。文獻[16]在基于能量均衡的基礎(chǔ)上，提出Mobile Data Collectors（MDCs）算法。首先，該算法從可移動基站開始進行周期性計算，將采用到的數(shù)據(jù)傳輸?shù)交?，并記錄其?shù)據(jù)傳輸過程中所經(jīng)歷過的節(jié)點，構(gòu)成網(wǎng)絡(luò)圖譜。其次，利用Warshall-Floyd算法構(gòu)造一個完整的圖，通過啟發(fā)式旅游規(guī)劃算法，實現(xiàn)整個網(wǎng)絡(luò)路由優(yōu)化過程。

上述文獻的路由算法均可以實現(xiàn)數(shù)據(jù)有效傳輸，但也存在一定不足。例如：算法復(fù)雜度過高，模型過于簡單，某些算法并未考慮能量問題。基于上述分析，本文主要從能量著手，以霧節(jié)點所映射到感知層的虛擬節(jié)點將傳感網(wǎng)所采集的數(shù)據(jù)上傳至霧層，并由功能強大的霧層節(jié)點對底層路由進行有效計算，從而節(jié)省整個網(wǎng)絡(luò)能量的開銷，延長了網(wǎng)絡(luò)生存周期。

2 網(wǎng)絡(luò)模型

2.1 基本假設(shè)與定義

為了更好地研究CCRP協(xié)議，本文基于以下假設(shè)：

（1）所有傳感器節(jié)點具有唯一ID，均勻分布在監(jiān)測區(qū)域內(nèi)。

（2）所有傳感器節(jié)點均處于靜態(tài)?；究梢苿?，能量不受限。

（3）初始時刻，所有傳感器節(jié)點均具有相同能量，并且地位平等。

（4）傳感器節(jié)點通信功率可控，即傳感器節(jié)點可以根據(jù)距離來調(diào)整發(fā)射功率的大小。

（5）節(jié)點具有感知能力、計算能力和數(shù)據(jù)融合能力。

定義1（能量效率）對于跨層分簇而言，在Δt 時間內(nèi)完成特定任務(wù)的能量效率為e 。也就是說，在t 時刻，單位能耗完成的任務(wù)數(shù)量為：

其中，n(Δt)表示為Δt 時間內(nèi)完成同樣任務(wù)數(shù)目，N 是簇內(nèi)所有節(jié)點數(shù)量，Ei(t)表示t 時刻節(jié)點i 的能量值。

定義2（能量均衡）在Δt 時刻，整個跨層分簇的能量均衡可以用能量均值函數(shù)ME(Δt)和能量方差函數(shù)DE(Δt) 來衡量網(wǎng)絡(luò)的能量均衡性，ME(Δt) 越大且DE(Δt)越小，則表示跨層分簇在Δt 時刻網(wǎng)絡(luò)能量均衡性越好。

定義3（網(wǎng)絡(luò)生存周期）從網(wǎng)絡(luò)開始運行至不能網(wǎng)絡(luò)無法正常工作為止，所持續(xù)的時間。也可以指從網(wǎng)絡(luò)部署之后到有所有節(jié)點死亡的時間。

定義4（數(shù)據(jù)匯聚時延）數(shù)據(jù)匯聚時延包括數(shù)據(jù)融合，跨層數(shù)據(jù)傳輸以及跨層路由轉(zhuǎn)發(fā)數(shù)據(jù)的時間的總和。

2.2 網(wǎng)絡(luò)模型的建立

在分簇路由協(xié)議中，將監(jiān)測區(qū)域內(nèi)所有傳感器節(jié)點劃分為多個簇。每一個簇可以充當(dāng)整網(wǎng)的一個子網(wǎng)，每個簇包括一個簇首節(jié)點（Cluster Head，CH）和多個簇成員節(jié)點（Cluster Member，CM）。簇成員通常是以直接方式將采用到的數(shù)據(jù)傳送給族首節(jié)點；當(dāng)簇的規(guī)模較大時，簇成員也可以通過多跳方式將數(shù)據(jù)傳送給簇首節(jié)點。簇首節(jié)點通過多跳或單跳方式與基站進行通信。簇首節(jié)點起到網(wǎng)關(guān)節(jié)點的作用，負責(zé)管理和控制簇內(nèi)成員節(jié)點，負責(zé)收集簇內(nèi)成員節(jié)點的感知數(shù)據(jù)，根據(jù)需要進行融合并轉(zhuǎn)發(fā)給基站。

當(dāng)?shù)讓觽鞲衅鞴?jié)點所采集數(shù)據(jù)較大時，借助于霧層來實現(xiàn)分簇路由協(xié)議。圖1給出了霧層分簇路由結(jié)構(gòu)，借助于霧層節(jié)點映射到傳感網(wǎng)中所形成的虛擬節(jié)點構(gòu)成傳感網(wǎng)的簇首節(jié)點完成路由協(xié)議選擇過程。霧層分簇是傳感網(wǎng)的一種新型分簇網(wǎng)絡(luò)結(jié)構(gòu)，這種結(jié)構(gòu)的設(shè)計思想是根據(jù)所要求采集數(shù)據(jù)量的大小達到的霧層，由霧節(jié)點加以融合與計算。在傳感網(wǎng)底層分簇的基礎(chǔ)上，利用由底層至上的原則繼續(xù)進行分簇。霧層的霧節(jié)點通過映射到傳感網(wǎng)底層所形成的虛擬節(jié)點構(gòu)成底層的簇首節(jié)點。以底層的簇首節(jié)點為中心，將簇內(nèi)成員所采集的數(shù)據(jù)傳至簇首節(jié)點，而后，通過虛擬節(jié)點所形成的簇首節(jié)點將數(shù)據(jù)繼續(xù)上傳到霧層，這樣就形成了跨層傳輸數(shù)據(jù)的具體過程。

圖1 基于霧層分簇路由結(jié)構(gòu)

傳感網(wǎng)傳輸能耗模型，在理想信噪比情況下傳輸k bit 的數(shù)據(jù)，能耗由兩部分構(gòu)成：發(fā)送k bit 長度數(shù)據(jù)的能量消耗和功率放大電路的能量消耗，根據(jù)傳輸距離的不同，發(fā)送數(shù)據(jù)能量消耗為：

其中，ETx(k,d)為傳輸距離（單位：m）為d 時傳輸k bit數(shù)據(jù)所消耗的能量，Eelec是傳輸或者接收單位數(shù)據(jù)的能耗；εfs和εmp分別為自由空間和多徑衰落模型中單位比特數(shù)據(jù)傳輸單位距離時放大器的能量損耗，d0是距離邊界閾值；若傳輸距離d ≤d0，選擇εfs，如果d ＞d0，即選擇εmp。

傳感網(wǎng)中，節(jié)點的能量主要用于通信和執(zhí)行指令?？鐚臃执鼐W(wǎng)絡(luò)中節(jié)點的通信可以分為3 種：簇內(nèi)通信、跨層報告和跨層數(shù)據(jù)轉(zhuǎn)發(fā)。簇內(nèi)通信主要完成簇內(nèi)成員節(jié)點與簇首節(jié)點之間的數(shù)據(jù)傳輸；跨層報告可以采用直接或間接傳輸方式把簇首節(jié)點融合后數(shù)據(jù)報告上傳至霧層；跨層數(shù)據(jù)轉(zhuǎn)發(fā)主要完成在傳感層與霧層之間距離匯聚節(jié)點較近的簇頭轉(zhuǎn)發(fā)距離較遠的簇首節(jié)點的數(shù)據(jù)。三者之間的關(guān)聯(lián)關(guān)系為：

其中，ETot表示節(jié)點的總通信能耗，Ein表示節(jié)點的簇內(nèi)通信能耗，ERep_lay表示跨層報告能耗；EFor_lay表示跨層節(jié)點的數(shù)據(jù)轉(zhuǎn)發(fā)能耗。在傳感層進行數(shù)據(jù)采集時，ERep_lay=0，EFor_lay=0，當(dāng)簇內(nèi)通信量較大或通信距離較遠時，ETot能量值較高，說明消耗網(wǎng)絡(luò)能量較大。

3 問題分析與解決方案

3.1 PSO算法概述

假設(shè)在一個D 維的目標(biāo)搜索空間中，群體規(guī)模為m ，群體中每一個粒子i(1 ≤i ≤m)有如下屬性：第t 步迭代時，在D 維空間中的位置為Xi(xi1,xi2,…,xid)，飛行速度為Vi=(vi1,vi2,…,vid)，經(jīng)歷過的最優(yōu)位置記為Pi=(pi1,pi2,…,pid)。在整個群體中，所有粒子經(jīng)歷過的最優(yōu)位置為Pg=(pg1,pg2,…,pgd)。在t 迭代的粒子根據(jù)下面公式更新自己的速度和位置：

其中，w 為慣性權(quán)重，c1和c2為加速因子，r1和r2是[0，1]之間的隨機數(shù)。在更新過程中，粒子每一維的位置和速度都被在允許范圍之內(nèi)。假設(shè)第d(1 ≤d ≤D)維的位置變化范圍為[-xdmax,xdmax] ，速度變化范圍為[-vdmax,vdmax]，迭代中如果位置和速度超過邊界范圍取邊界值。vdmax的選擇取值范圍為[0.1，0.3]之間。如果vdmax太大，粒子運動軌跡可能失去規(guī)律性，甚至越過最優(yōu)解所在區(qū)域；如果太小，可能降低粒子的全局搜索能力，算法可能陷入局部最優(yōu)解。

為了避免陷入局部最優(yōu)解，本文CCRP算法采用加速因子雙重迭代過程增強局部搜索與全局搜索能力；其次，在本過程實施階段，為了提高收斂速度，本文CCRP算法采用降低c1因子數(shù)值的同時提高c2因子數(shù)值，其迭代公式如下：

其中，k 代表CCRP 算法當(dāng)前迭代次數(shù)；cn為迭代結(jié)束前最后一次迭代數(shù)值；Tmax為最大迭代次數(shù)。

其主要目的在于：粒子群優(yōu)化算法是尋找全局最優(yōu)解的智能算法。本文采用雙因子相制約思想，即：當(dāng)c1減少的同時增加c2，可以更好地平衡簇內(nèi)收斂過快，而產(chǎn)生過早陷入最優(yōu)解的不足；經(jīng)過一輪或多輪周期后，該簇內(nèi)的所有成員節(jié)點位置信息均處于平衡狀態(tài)；如果單純地增加慣性權(quán)重w 的數(shù)值，雖然可以獲得較為理想的新位置信息的同時也可以避免“早熟”現(xiàn)象，但是其算法的收斂速度將會變慢，不利用于全局優(yōu)化。對于整個監(jiān)測區(qū)域而言，本文利用上述過程，采用多次重復(fù)上述操作完成對整個監(jiān)測區(qū)域的位置的優(yōu)化，從而達到了全局優(yōu)化的目的。

3.2 簇的建立

傳感網(wǎng)底層應(yīng)用PSO算法實現(xiàn)網(wǎng)絡(luò)分簇。首先，基于所有節(jié)點的能量信息，由霧節(jié)點（Fog Node，F(xiàn)N）計算節(jié)點的平均能量且大于或等于全網(wǎng)的平均能量時，該節(jié)點將成為候選簇首節(jié)點，這樣可以有效地縮減簇首節(jié)點的選擇范圍同時保證了候選簇首節(jié)點具有較大的能量。

假設(shè)網(wǎng)絡(luò)包含N 個節(jié)點，預(yù)先定義分為K 個簇，候選簇首數(shù)量為M ，且M ＞K，則可能的分簇方式有C種，在其中確定最佳的分簇方式是一種最優(yōu)化問題。應(yīng)用PSO算法解決這個問題，使每一個粒子代表一種可能的分簇方式，用目標(biāo)函數(shù)評價其性能，設(shè)置m 個粒子組成群體在C種可能的分簇方式中尋找最優(yōu)解，使目標(biāo)函數(shù)取得最小值。該目標(biāo)函數(shù)定義如下：

其中，f1為分簇緊湊性評價因子，等于節(jié)點至霧點映射到傳感網(wǎng)底層的虛擬節(jié)點最大平均歐氏距離。d(ni,CH(p,k))是節(jié)點ni到映射霧節(jié)點（Map Fog Node，MFN）的歐氏距離，|C(p,k)|是粒子p 中簇Ck的節(jié)點數(shù)量；f2為簇頭能量評價因子，等于網(wǎng)絡(luò)中所有節(jié)點ni,i=1,2,…,N當(dāng)前能量之和簇首當(dāng)前能量之和的商；β 為各評價因子的權(quán)重系數(shù)。

定理1在面積為L2正方形區(qū)域中，完成傳感網(wǎng)底層到霧層分簇路由的最優(yōu)簇的數(shù)量為：

其中，dacr為數(shù)據(jù)壓縮率，為簇首節(jié)點到霧節(jié)點距離，為簇首節(jié)點到映射霧節(jié)點距離，N 是傳感器節(jié)點數(shù)量。

證明網(wǎng)絡(luò)的最優(yōu)分簇數(shù)，可以通過計算網(wǎng)絡(luò)每輪消耗的能量來求解。PSO 分簇算法和映射霧節(jié)點的確定可以霧層中完成，不消耗節(jié)點能量。通過映射霧節(jié)點確定最優(yōu)簇首組合和簇內(nèi)節(jié)點數(shù)量。假設(shè)控制報文發(fā)送消息長度為k，網(wǎng)絡(luò)節(jié)點數(shù)量為N ，則該時刻網(wǎng)絡(luò)消耗的能量為：

在網(wǎng)絡(luò)穩(wěn)定階段，K 個簇首接收各自成員節(jié)點發(fā)送的k bit數(shù)據(jù)包，將這些數(shù)據(jù)和自身的數(shù)據(jù)事例為k bit數(shù)據(jù)包后發(fā)給映射節(jié)點。數(shù)據(jù)融合的能量開銷為ED，則該階段所有簇首消耗的能量為：

簇內(nèi)每個成員節(jié)點發(fā)送k bit 數(shù)據(jù)包至簇首節(jié)點所消耗的能量為：

其中，CNi表示第i 個簇節(jié)點數(shù)量。由于簇的規(guī)模一般來說比較小，成員節(jié)點至簇頭的距離通常小于d0，每個簇所占二維區(qū)域的面積為：

簇內(nèi)成員節(jié)點的數(shù)量為N/K 。一般情況下，這是一個節(jié)點頒布密度ρ(x,y)的任意形狀區(qū)域。假設(shè)簇首位于簇區(qū)域的中心，則：

為了計算方法，把簇形區(qū)域近似看作為圓形區(qū)域，其半徑為：

由于數(shù)據(jù)壓縮和數(shù)據(jù)融合所消耗的傳感器節(jié)點能量較小，因此dacr×Eelec+ED值近似為0，公式（27）化簡可得：

3.3 簇的形成

簇首節(jié)點利用PSO算法在其鄰居簇首集合中，選擇其中繼節(jié)點RNi，中繼節(jié)點RNi在所有的候選節(jié)點中上具有最小的代價函數(shù)，定義如下：

其中，Ene(si)表示簇首si的鄰居簇首剩余能量均值，Ecu(sj)表示簇首sj的剩余能量均值；NCH(sj)表示簇首sj的成員節(jié)點數(shù)量；NCH(si)表示簇首si的鄰居簇首成員節(jié)點數(shù)量的均值；d|si-sj|表示簇首si到簇首sj的距離；d|sj-sFN|表示簇首到霧節(jié)點之間的距離。α1、α2、α3為權(quán)重系數(shù)，且α1+α2+α3=1 。因此，Cost(RNi)=min{Cost(i,j)}。如果簇首si的中繼節(jié)點是本身，則直接發(fā)送數(shù)據(jù)至映射霧節(jié)點；否則，簇首si發(fā)送數(shù)據(jù)至中繼節(jié)點RNi。

在跨層分簇結(jié)構(gòu)中，映射霧節(jié)點完成一次任務(wù)，即接收其成員節(jié)點和下層簇首節(jié)點的數(shù)據(jù)并完成數(shù)據(jù)融合，并向上層霧節(jié)點或基站轉(zhuǎn)發(fā)融合后的數(shù)據(jù)。如果映射霧節(jié)點中成員太多，則可能導(dǎo)致該映射霧節(jié)點在一次任務(wù)中能量消耗過盡，而無法完成本次任務(wù)，這會造成網(wǎng)絡(luò)傳輸數(shù)據(jù)的失敗。同時，如果簇中成員太少，導(dǎo)致映射霧節(jié)點主要完成轉(zhuǎn)發(fā)來自其他簇首的數(shù)據(jù)，使其在網(wǎng)絡(luò)失效時存在大量的剩余能量，從而使其能量沒有充分利用。因此，合理地控制簇的規(guī)模對于網(wǎng)絡(luò)性能來說至關(guān)重要。

設(shè)n個節(jié)點為均勻分布在簇成員節(jié)點和霧節(jié)點之間，相鄰節(jié)點間的距離為單跳d1-hop，節(jié)點的線性表示形式為圖2所示。

圖2 節(jié)點線性數(shù)據(jù)傳輸結(jié)構(gòu)

定理2能量衰減系數(shù)為2，其單跳距離d1-hop=dopt+Δd的能耗增量小于單跳距離為d1-hop=dopt-Δd能耗增量。其中，dopt為最低目標(biāo)最優(yōu)單跳距離。

證明以圖2 為例，設(shè)線性節(jié)點分簇數(shù)量為1，傳輸數(shù)據(jù)為kbit，根據(jù)公式（7）可得：

3.4 算法描述及復(fù)雜度計算

本文CCRP 算法的核心思想是綜合考慮傳感網(wǎng)層與霧層之間的節(jié)點度和與映射區(qū)域中心距離兩個因素，通過時間片輪轉(zhuǎn)更換簇頭節(jié)點，以均衡簇頭節(jié)點的能量消耗，以解決無線傳感器網(wǎng)絡(luò)分簇中的“熱區(qū)”問題。算法步驟如下：

步驟1初始化Q個粒子，每個粒子包含K個候選簇首節(jié)點，每個候選簇首節(jié)點代表一種分簇的可能。

步驟2計算每個粒子p的適用值。

（1）對每個節(jié)點ni(i=1,2,…,N)和所有簇首CH的距離d(ni,CH)。分配節(jié)點ni給距離最近的簇首節(jié)點，即：

（2）利用公式（12）～（14）、（30）、（31）分別計算粒子適應(yīng)值，并保存在鏈表中。

步驟3通過定理1 計算最優(yōu)K值的取值范圍，并確定每個粒子的個體最優(yōu)解和種群的最優(yōu)解。

步驟4利用公式（8）、（9）更新粒子速度與位置。

步驟5根據(jù)距離最近的候選簇首位置調(diào)整粒子位置。

步驟6重復(fù)步驟2至步驟5，直到定理2成立。

假設(shè)N=T×M個節(jié)點成為候選簇首節(jié)點而參與競選，共廣播T×M條消息。然后，競選成功的候選簇首節(jié)點廣播一條消息，其鄰居節(jié)點收到消息后直接退出競選。假設(shè)共選出K個簇首節(jié)點，則它們廣播K條發(fā)送消息和K條接收消息，而M-K個簇成員廣播MK條成簇消息。因此，該階段網(wǎng)絡(luò)中總的消息開銷為：

所以本文CCRP算法的復(fù)雜度為O(N)。

4 體系評估

為了進一步驗證本文CCRP 算法的有效性和實效性，本文采用MATLAB 8.0 作為仿真實驗平臺，并與文獻[13]和文獻[15]以及文獻[16]在網(wǎng)絡(luò)節(jié)點存活數(shù)量、剩余能量、網(wǎng)絡(luò)生存周期等屬性上進行比對實驗。本文采用800個傳感器節(jié)點隨機部署500 m×500 m正方形監(jiān)測區(qū)域，數(shù)據(jù)總長度為1 000 bit，數(shù)據(jù)包頭為50 bit，簇的數(shù)量設(shè)定為總傳感器節(jié)點數(shù)量的2%至5%以內(nèi)，即K∈[16，40]，傳感器節(jié)點感知半徑R=10 m。PSO算法設(shè)定為種群Q=20，c1=2，c2=3，慣性權(quán)重參數(shù)w∈[0.4，0.9]，評價因子α1∈[0.1，0.4]，α2∈[0.1，0.4]，α3∈[0.2，0.8]，且α1+α2+α3=1，節(jié)點初始能量為5 J。

圖3 t=0時，500 m×500 m網(wǎng)絡(luò)節(jié)點分布示意圖

圖4 t=500 s時，500 m×500 m網(wǎng)絡(luò)節(jié)點分布示意圖

圖5 t=1 000 s時，500 m×500 m網(wǎng)絡(luò)節(jié)點分布示意圖

圖6 t=1 500 s時，500 m×500 m網(wǎng)絡(luò)節(jié)點分布示意圖

圖7 t=2 000 s時，500 m×500 m網(wǎng)絡(luò)節(jié)點分布示意圖

圖3至圖7給出了不同t時刻下，網(wǎng)絡(luò)節(jié)點分布示意圖。采用的參數(shù)為w=0.6,α1=0.1,α2=0.3,α3=0.6。從圖中可以看出，隨著時間t的推移，出現(xiàn)了部分節(jié)點死亡現(xiàn)象。當(dāng)t=500 s 時，死亡節(jié)點數(shù)量為8；當(dāng)t=1 000 s時，死亡節(jié)點數(shù)量為47；當(dāng)t=1 500 s時，死亡節(jié)點數(shù)量為66；當(dāng)t=2 000 s 時，死亡節(jié)點數(shù)量為73。當(dāng)t=1 500 s和t=2 000 s時，死亡節(jié)點趨于一種穩(wěn)定狀態(tài)，其網(wǎng)絡(luò)系統(tǒng)節(jié)點存活率為91.75%和90.88%。其主要原因在于本文CCRP 協(xié)議采用PSO 算法與霧計算相結(jié)合方法實現(xiàn)節(jié)點能量快速消耗。CCRP 協(xié)議有效地平衡了靠近映射霧節(jié)點的簇和遠離映射霧節(jié)點的簇之間的數(shù)據(jù)傳輸能耗。CCRP 協(xié)議的死亡節(jié)點較均勻地分布在整個網(wǎng)絡(luò)，可以有效地避免了“能量空洞”的出現(xiàn)。

圖8至圖11給出了不同參數(shù)下的四種算法剩余能量對比示意圖。從圖中可以看出，隨著時間的推移，四種算法節(jié)點剩余能量均有所消耗，但本文CCRP協(xié)議的能量消耗速度明顯低于其他三種算法。本文算法在圖8和圖9中能量消耗速度較快，但整個網(wǎng)絡(luò)的總體能量還是高于其他三種算法。其主要原因在于其他三種算法均采用非連續(xù)單跳方式連續(xù)地將數(shù)據(jù)傳輸給基站，當(dāng)基站距離傳感網(wǎng)較遠時，將會導(dǎo)致簇首節(jié)點向基站傳輸數(shù)據(jù)的能耗較大，不利于抑制節(jié)點節(jié)能作用；而本文CCRP協(xié)議利用映射霧節(jié)點完成簇間多跳路由數(shù)據(jù)傳輸。通過改變參數(shù)可以有效地抑制節(jié)點能量的快速消耗。當(dāng)映射霧節(jié)點距離網(wǎng)絡(luò)較遠時，可以通過改變權(quán)重參數(shù)提升PSO算法遍歷速度，已達到快速完成數(shù)據(jù)傳輸效果；通過適應(yīng)函數(shù)和代價函數(shù)提升PSO算法對整個網(wǎng)絡(luò)全局搜索效果，最終達到了快速與低能相結(jié)合的數(shù)據(jù)傳輸目的。

圖8 不同參數(shù)下四種算法剩余能量對比

圖9 不同參數(shù)下四種算法剩余能量對比

圖10 不同參數(shù)下四種算法剩余能量對比

圖11 不同參數(shù)下四種算法剩余能量對比

圖12 不同參數(shù)下四種算法網(wǎng)絡(luò)生存周期對比

圖13 不同參數(shù)下四種算法網(wǎng)絡(luò)生存周期對比

圖12至圖15給出的是不同參數(shù)下四種算法網(wǎng)絡(luò)生存周期對比示意圖。在圖12 和圖13 是以低密度節(jié)點100至400變化作為網(wǎng)絡(luò)生存周期研究的變量。從圖中可以看出，隨著傳感器節(jié)點數(shù)量的增加，四種算法的網(wǎng)絡(luò)生存周期均有明顯的提升，但本文CCRP協(xié)議提升的速度較快。圖14 和圖15 給出的高密度節(jié)點從450 至800 變化的網(wǎng)絡(luò)生存周期對比示意圖。從圖中可以看出，當(dāng)傳感器節(jié)點數(shù)量為500時，本文CCRP協(xié)議基本上趨于平穩(wěn)，變化的幅度較小，而其他三種算法雖然有上升趨勢，但并未超過本文CCRP 協(xié)議，從而驗證了本文算法的網(wǎng)絡(luò)生存周期優(yōu)于其他三種算法。主要原因在于，本文利用映射霧節(jié)點完成了對數(shù)據(jù)融合和傳輸?shù)热蝿?wù)，分擔(dān)了部分簇首的工作量，抑制了簇首節(jié)點能量的快速消耗；同時，在數(shù)據(jù)融合和傳輸中，映射霧節(jié)點充當(dāng)了控制節(jié)點的作用，對簇首節(jié)點和簇內(nèi)成員節(jié)點進行統(tǒng)一的調(diào)節(jié)與分配，從而節(jié)省了簇內(nèi)能量的開銷，延長了網(wǎng)絡(luò)生存周期。

圖14 不同參數(shù)下四種算法網(wǎng)絡(luò)生存周期對比

圖15 不同參數(shù)下四種算法網(wǎng)絡(luò)生存周期對比

5 總結(jié)

本文借助霧計算理論的同時引入粒子群優(yōu)化算法，提出了一種基于霧計算跨層感知分簇路由協(xié)議（CCRP）。該協(xié)議首先通過霧計算理論構(gòu)建網(wǎng)絡(luò)模型，通過跨層映射原理，利用感知事件驅(qū)動機制將霧節(jié)點映射到傳感層；其次，給出了以邊長為L正方形區(qū)域的最優(yōu)簇建立的方法和計算過程；再次，分析了簇的形成以及跨層分簇結(jié)構(gòu)數(shù)據(jù)融合過程，從而建立以映射霧節(jié)點為中心的優(yōu)化數(shù)據(jù)聚合路由，取代傳感網(wǎng)底層路由中的數(shù)據(jù)，進一步平衡并減少網(wǎng)絡(luò)負載。本文最后通過仿真實驗驗證本文協(xié)議的有效性和實效性。未來的主要工作集中在連續(xù)性分簇路由優(yōu)化以及非線性的連續(xù)覆蓋。