低能耗和低時延的無線傳感器網(wǎng)絡(luò)數(shù)據(jù)融合算法

摘要：針對無線傳感器網(wǎng)絡(luò)的節(jié)點能量有限，且在進行信息傳輸時存在數(shù)據(jù)沖突、傳輸延時等問題，提出并設(shè)計了基于最大生存周期的無線傳感器網(wǎng)絡(luò)數(shù)據(jù)融合算法。該算法將整個網(wǎng)絡(luò)中的節(jié)點分成多個簇，并根據(jù)節(jié)點的傳輸范圍，將每個簇中的節(jié)點均勻分布，每個節(jié)點根據(jù)自己的本地信息和剩余能量選擇通信方式向簇頭節(jié)點傳輸數(shù)據(jù)，從而形成傳輸數(shù)據(jù)的最短路徑；并根據(jù)集中式TDMA(時分多址)調(diào)度模型，運用基于微粒群的Pareto優(yōu)化方法，使得網(wǎng)絡(luò)在完成規(guī)定的信息傳輸時每個節(jié)點耗費的平均時隙和平均能耗最優(yōu)。仿真結(jié)果表明，上述算法不但可以最大化網(wǎng)絡(luò)的生存時間，還可以有效的降低數(shù)據(jù)融合時間，減少網(wǎng)絡(luò)延時。
關(guān)鍵詞：無線傳感器網(wǎng)絡(luò)；數(shù)據(jù)融合；能耗；延時；時分多址；微粒群；生存時間；Pareto優(yōu)化

    無線傳感器網(wǎng)絡(luò)(Wireless Sensor Network，WSN)是由分布在檢測區(qū)域內(nèi)大量的靜止或移動的傳感器組成，它們是通過自組織和多跳的方式形成的無線網(wǎng)絡(luò)，可以協(xié)作地感知、采集和處理檢測區(qū)內(nèi)的各種信息，并把信息傳送給用戶終端，是一種新興的信息獲取和處理技術(shù)。WSN可應(yīng)用于惡劣環(huán)境和無人環(huán)境下信息的采集和傳送，同時，它還具有布設(shè)靈活、成本低、范圍大等特點，日益受到人們的關(guān)注，是當(dāng)前國際備受關(guān)注的研究熱點之一。
    在無線傳感器網(wǎng)絡(luò)中，若各個節(jié)點在采集信息時，采用單獨傳送信息到匯聚節(jié)點的方法，則會造成網(wǎng)絡(luò)過多能量的消耗和傳輸信息的頻繁沖突碰撞。因此，使用數(shù)據(jù)融合的方法來減少網(wǎng)絡(luò)中信息傳輸?shù)目偭?，從而達到節(jié)能和提高信息傳輸效率的目的。它不但可以采用一定的算法將傳感器節(jié)點采集到的大量原始數(shù)據(jù)進行網(wǎng)內(nèi)處理，去除其中的冗余信息，而且還可以在融合前減少匯聚節(jié)點等待非匯聚節(jié)點信息
傳輸?shù)臅r間，減少網(wǎng)絡(luò)中數(shù)據(jù)融合的延時時間。

1 無線傳感器網(wǎng)絡(luò)的數(shù)據(jù)融合算法
1．1 數(shù)據(jù)融合概念的描述
    在無線傳感器網(wǎng)絡(luò)中，數(shù)據(jù)融合是在一定的準(zhǔn)則下對按時間順序獲得的若干傳感器節(jié)點的檢測信息進行自動分析、融合，以完成所需要的估計任務(wù)和決策進行的信息處理過程。
1．2 節(jié)點剩余能量的計算
    假定節(jié)點的初始能量為Er，并且在T1時刻之前，網(wǎng)絡(luò)分別進行了n1次、n2次的信息發(fā)送和接收，則節(jié)點i存T1時刻的剩余能量可用公式(1)表示
   

2 低功耗無線傳感器網(wǎng)絡(luò)數(shù)據(jù)融合算法
2．1 節(jié)點數(shù)據(jù)結(jié)構(gòu)
    傳感器節(jié)點i需要維護的信息包括：1)簇頭節(jié)點Pi；2)節(jié)點的剩余能量標(biāo)志位Hi：設(shè)置能量閾值ST，若節(jié)點i剩余能量值為Si，當(dāng)Si<ST時，則置Hi=0，并通知鄰節(jié)點不再向i發(fā)送信息；否則置Hi=1，可以進行下一次信息的接收或者發(fā)送。
2．2 算法描述
    假設(shè)在檢測區(qū)域內(nèi)存在多個傳感器節(jié)點，我們將其分為多個簇。而后根據(jù)各個傳感器節(jié)點的傳輸距離，對每個簇內(nèi)的節(jié)點進行均勻布置，如圖1所示。

    首先，根據(jù)網(wǎng)絡(luò)中每個節(jié)點的自身信息來決定各個簇頭節(jié)點，而后由它們來啟動數(shù)據(jù)融合算法。由于網(wǎng)絡(luò)中各個簇頭節(jié)點的選取都取決于自身的信息，因而會導(dǎo)致網(wǎng)絡(luò)的結(jié)構(gòu)和每個節(jié)點的位置處于不斷變化之中，若選取幾個固定的節(jié)點勢必會造成較大時間延時和能量消耗?；谏鲜鲈?，為了保證每次選取的初始節(jié)點不同，應(yīng)該選擇距離基站最遠的節(jié)點作為初始節(jié)點，由它們啟動融合算法，從而最短化簇頭節(jié)點到基站的距離，降低數(shù)據(jù)融合的延時和能耗，最大化網(wǎng)絡(luò)的生存周期。
    每個簇中數(shù)據(jù)傳輸?shù)倪^程為：首先，簇頭節(jié)點檢測自身的剩余能量Si，若Si>ST，置Hi=1，并向所有可到達的傳感器節(jié)點發(fā)布自己的位置信，否則簇頭節(jié)點廣播信息使得其他節(jié)點進入休眠狀態(tài)。我們假設(shè)簇頭節(jié)點的剩余能量Si>ST，則簇頭節(jié)點向非簇頭節(jié)點廣播自己的位置信息，非簇頭節(jié)點i在接收到這一信息后，判斷自己到簇頭節(jié)點的最小跳數(shù)和距離其最近的節(jié)點i的剩余能量，若其剩余能量Si大于能量閥值ST，且到簇頭節(jié)點的跳數(shù)小于節(jié)點i到簇頭的跳數(shù)，則節(jié)點i選擇節(jié)點j作為父節(jié)點，并向父節(jié)點j發(fā)送加入請求，否則置Hj=0、Fj=0，告訴鄰近的節(jié)點不要再向j發(fā)送信息，并使自己進入長期休眠狀態(tài)，而后節(jié)點i重復(fù)上述過程，直到選出父節(jié)點為止。
    如圖1，簇頭節(jié)點9首先啟動運算并檢測自身的剩余能量值S9，若S9<ST，則置H9=0，并向其它節(jié)點廣播信息，使其它節(jié)點進入休眠狀態(tài)；若S9>ST，則置H9=1，而后簇頭節(jié)點9把自己所在的位置告訴鄰近的非簇頭節(jié)點，由它們自己判斷到簇頭節(jié)點9的最小跳數(shù)和剩余能量，并把信息反饋給簇頭節(jié)點9，由其選擇那些非簇頭節(jié)點可以加入其為簇頭節(jié)點的簇內(nèi)。圖1中，節(jié)點1判斷自己到簇頭節(jié)點9的跳數(shù)為4跳，且距離其最近的非簇頭節(jié)點4的剩余能量為S4，雖然節(jié)點4距簇頭節(jié)點最小跳數(shù)為3跳小于節(jié)點1到簇頭節(jié)點的跳數(shù)，但是由于S4小于ST，節(jié)點4仍不能作為節(jié)點1的父節(jié)點，而后繼續(xù)判斷距離簇頭節(jié)點9較遠但到簇頭節(jié)點9的跳數(shù)仍為3跳的節(jié)點5的剩余能量，由于S5大于ST，所以節(jié)點1選擇節(jié)點5作為父節(jié)點，同理，5的父節(jié)點為7，7的父節(jié)點點為8，8的父節(jié)點為簇頭節(jié)點9，至此一個簇建立完畢。
2．3 時隙分配方案
    節(jié)點在信息傳輸?shù)倪^程中，可能存在空閑偵聽、傳輸碰撞等現(xiàn)象，從而導(dǎo)致傳感器網(wǎng)絡(luò)在進行信道訪問時存在較大的時延和能量消耗，因此設(shè)計了一種新的TDMA調(diào)度方案，并運用基于微粒群的Pareto(簡稱PAPSO)優(yōu)化方法，使得無線傳感器網(wǎng)絡(luò)在完成規(guī)定的信息傳輸任務(wù)時每個節(jié)點的平均時隙和平均能耗最優(yōu)。
2．3．1 優(yōu)化目標(biāo)
    把初始節(jié)點傳送的信息在經(jīng)過單跳或多跳通信方式到簇頭節(jié)點的過程，稱為一個事件，信息每次跳轉(zhuǎn)傳輸?shù)倪^程稱為一個子事件，一個子事件對應(yīng)一個執(zhí)行節(jié)點，并占用一個時隙，則無線傳感器網(wǎng)絡(luò)完成指定任務(wù)每個節(jié)點的平均時隙和平均能耗分別以f1和f2表達，如下所示。

    完成此次傳輸事件時的總接收時間。通過公式(2)和(3)可知，通過減少網(wǎng)絡(luò)中各個環(huán)節(jié)的切換能量和時隙的個數(shù)，就可以最大化網(wǎng)絡(luò)的生存周期。
2．3．2 個體的編碼與解碼規(guī)則
    要優(yōu)化TDMA分配，首先應(yīng)找到事件與問題間的對應(yīng)關(guān)系，而后在解的空間內(nèi)搜索最優(yōu)解，由2．3．1節(jié)可知，把信息傳輸?shù)倪^程看作是由一系列子事件組成的，因此一個事件可被記為(事件編號，順序號)，其中，事件編號是指該子事件屬于那個事件，順序號則指信息傳輸過程中每一個子事件執(zhí)行的順序編號。
    綜上，可以將每個無沖突的事件按一個順序進行編碼，繼而按順序給它們分配時隙。這就是由編碼規(guī)則得到的個體與TDMA調(diào)度方案之間的映射關(guān)系的解碼規(guī)則。
2．3．3 基本粒子群算法
    粒子群算法最早是由Kenney和Eberhart在1995年提出的，是一種新的模仿鳥類群體行動的自能優(yōu)化方法，縮寫為“PSO”，它與遺傳算法一樣，是從隨機解出發(fā)的，可通過適度評價解的好壞，并通過迭代的方法尋找最優(yōu)解。PSO迭代方程如下：
   
    其中：“i”表示微粒：“d”表示微粒的第d維；“t”表示第t代；Vid表示微粒i的速度；Xid表示微粒i的位置；Pid表示微粒i的個體極值(p_best)，Pgl表示所有微粒i全局極值(g_best)；W表示慣性權(quán)重；C1、C2表示學(xué)習(xí)因子；r1、r2表示介于(0，1)之間的隨機數(shù)。
2．3．4 多目標(biāo)微粒群算法解的評價機制
    在多目標(biāo)優(yōu)化問題中，可以用多目標(biāo)的加權(quán)和方法和Pareto優(yōu)化方法作為評價機制為微粒群的搜索方向提供依據(jù)。
    PSO是粒子通過跟蹤兩個“極值”來為自己提供搜索方向的，一個是粒子本身的p_best，另一個則是g_best，因此使用粒子的p_best和g_best相結(jié)合的方式對多目標(biāo)解進行評價。
    1)粒子自身p_best的評價

    2)全局最優(yōu)解的評價
    TDMA調(diào)度中是以任務(wù)完成時每個節(jié)點的平均時隙數(shù)和平均能耗最優(yōu)作為指的標(biāo)，但由于在一定的任務(wù)條件下，要求每個節(jié)點的平均能耗和平均時隙最優(yōu)，即是要求節(jié)點工作的連續(xù)性很好，即是要求父節(jié)點應(yīng)接收完所有子節(jié)點傳送的信息后，才進行下一次信息跳轉(zhuǎn)的傳輸，這樣必會增加節(jié)點的平均時隙數(shù)，反之亦然。由于任務(wù)完成時每個節(jié)點的平均時隙數(shù)和平均能耗不能同時達到最優(yōu)，加權(quán)和方法很難完全評價解的好壞，因此，引入Pareto優(yōu)化方法，來評價解的好壞。對于一個最小化M個目標(biāo)的問題，使用支配概念，其定義如下：minF=[f1，f2，…，fM]，若要X1支配X2，則在解空間內(nèi)必存在任意兩個解X1、X2滿足如下條件：
    ①在解空間內(nèi)，一定存在一個X2比X1大，即fj(X1)≯fj(X2)，j∈(1，2，…，M)；
    ②X2一定有一個在目標(biāo)上是嚴(yán)格比X1大的，即fj(X1)<fj(X2)。
    如果解不滿足①和②中的任意一條，則稱X1不支配X2，即X1是X2的非支配解，所有的非支配解構(gòu)成非支配解集，若非支配解的求取是在整個解空間內(nèi)進行時，則稱該非支配解為Pareto最優(yōu)解。
2．3．5 PAPSO優(yōu)化方法實施步驟
    PAPSO實施步驟：
    1)對粒子進行初始化，即設(shè)定粒子的個數(shù)為np，迭代次數(shù)Nmax，產(chǎn)生np個隨機初始值X；并初始化W、C1、C2、和p_best的值，并把當(dāng)前的粒子位置設(shè)置為p_best；用評價機制對粒子的p_best進行評價，找到g_best，而后計算出目標(biāo)函數(shù)F中的每個目標(biāo)值，用Pareto優(yōu)化概念，找出作用于整個解空間的非支配解，從而初步形成一個Pareto解集。
    2)進行迭代運算，用式(4)和式(5)產(chǎn)生下一代微粒群。
    3)應(yīng)用評價機制對X(j)和p_best(j)進行評價；如果f(X(j))>f(p_best(j))，則p_best(j)=X(j)；更新所有個體的最優(yōu)位置和全局的最優(yōu)位；應(yīng)用支配的概念，找出非支配解集，進而找出Pareto解集。
    4)滿足迭代條件(有此以迭代代數(shù)作為條件)，輸出最后一代的種群個體(即Pareto最優(yōu)解集)；否則，執(zhí)行步驟3)。

3 仿真及其分析
    在一個二維環(huán)境中進行試驗，169個節(jié)點被均勻的放置在600 m2的網(wǎng)格區(qū)域中。
    仿真試驗中，每個節(jié)點的信道容量為500kbs，并在可以形成鏈接的通信范圍內(nèi)，設(shè)定通信距離為15m。節(jié)點活動狀態(tài)和睡眠狀態(tài)的切換時間是470μs。以一個數(shù)據(jù)包的傳輸時間和可能的時鐘偏移時間之和作為TDMA時隙的大小。發(fā)送和接收一個數(shù)據(jù)包所需的功率是81mW和180mW。
    基于上述的網(wǎng)絡(luò)模型，分別對LEACH、DEEC及新算法進行了仿真，重點比較和分析了3種路由算法運行過程中網(wǎng)絡(luò)的生命周期。
    圖2為運行過程中整個網(wǎng)絡(luò)生命周期對比的仿真。由圖可見，如果一個網(wǎng)絡(luò)中節(jié)點的初始數(shù)目相同，新算法可以使得網(wǎng)絡(luò)的生命周期最長，LEACH算法在大約40％的節(jié)點死亡之前，其性能比DEEC算法差，而后它的性能要優(yōu)于DEEC算法。由于新算法選擇簇頭時考慮了節(jié)點的剩余能量，當(dāng)節(jié)點剩余能量較小的時候，將選擇距離其最近的節(jié)點作為簇頭，繼續(xù)進行信息的傳輸，且由于選擇了最短傳速路徑和最優(yōu)了時隙分配方案，所以在完成傳輸任務(wù)是每個節(jié)點消耗的平均能量和平均時隙最優(yōu)，最大化了網(wǎng)絡(luò)的生存周期。

    仿真實驗還比較了NBSA算法和PAPSO優(yōu)化方法用于TDMA調(diào)度方案時，網(wǎng)絡(luò)中每個節(jié)點在完成規(guī)定任務(wù)時的平均能耗和平均時隙。在多目標(biāo)粒子群Pareto優(yōu)化方法中，取C1、C2和W分別2．0和1．5，微粒群的個數(shù)為40，迭代次數(shù)為600。
    從表1不難看出PAPS01雖然平均能耗是7個中最差的，但平均時隙卻是7個中最少的，而PAPS07則與PAPS01相反，平均能耗雖是7個中最少的，但平均時隙卻是最多的。它們之間分還布著其余5個解。

    由于這7個解的是均勻分布的，因此，目標(biāo)f1、f2的中間解為PAPS04。依Pareto優(yōu)化概念對各算法的結(jié)果進行分析，由圖3顯見，PAPSO(1—4)對NBSA構(gòu)成支配。可見多目標(biāo)粒子群Pareto優(yōu)化方法能得到比NBSA更好的調(diào)度結(jié)果。

4 結(jié)論
    在無線傳感器網(wǎng)絡(luò)中，為減少信息傳輸過程中的時延和能耗，提出了基于最大生存周期的數(shù)據(jù)融合算法，并結(jié)合對TDMA調(diào)度，提出了相對應(yīng)的PSO—Pareto優(yōu)化方法，從而在信息傳輸?shù)穆窂胶兔總€節(jié)點完成規(guī)定任務(wù)所需的平均時隙、平均能耗兩個方面論述了減少網(wǎng)絡(luò)的時延和能耗，最大化了網(wǎng)絡(luò)的生存周期和最小化了網(wǎng)絡(luò)的延時。