一種基于信息熵的WSN節(jié)點(diǎn)擁塞避免機(jī)制

摘要：無(wú)線傳感器網(wǎng)絡(luò)(WSN)中多對(duì)一通信產(chǎn)生的網(wǎng)絡(luò)擁塞是一個(gè)亟待解決的問(wèn)題。針對(duì)WSN節(jié)點(diǎn)生命期有限的情況，引入了節(jié)點(diǎn)相對(duì)信息熵的概念，提出基于節(jié)點(diǎn)相對(duì)信息熵的擁塞避免機(jī)制：節(jié)點(diǎn)首先計(jì)算其聯(lián)合信息熵為上游節(jié)點(diǎn)分配數(shù)據(jù)窗；然后上游節(jié)點(diǎn)根據(jù)收到的數(shù)據(jù)窗的大小來(lái)決定向下游節(jié)點(diǎn)發(fā)送數(shù)據(jù)包的大小。仿真分析表明，該算法有效地避免了網(wǎng)絡(luò)數(shù)據(jù)包的丟失，減少了網(wǎng)絡(luò)傳輸延遲，且具有良好的能量有效性。
關(guān)鍵詞：無(wú)線傳感器網(wǎng)絡(luò)；節(jié)點(diǎn)相對(duì)信息熵；擁塞避免；數(shù)據(jù)窗

0 引言
    與物理世界緊密耦合的無(wú)線傳感器網(wǎng)絡(luò)(WSN)具有大規(guī)模密集部署、節(jié)點(diǎn)資源受限、無(wú)線帶寬小、拓?fù)浣Y(jié)構(gòu)動(dòng)態(tài)變化等特點(diǎn)。其節(jié)點(diǎn)采集到的數(shù)據(jù)以多跳的方式發(fā)送到基站。這種多對(duì)一的數(shù)據(jù)傳輸方式以及待檢測(cè)事件的突發(fā)性，使得能量、處理能力及通信能力都受限的WSN在數(shù)據(jù)傳輸過(guò)程中經(jīng)常發(fā)生擁塞，從而導(dǎo)致數(shù)據(jù)包的大量丟失和網(wǎng)絡(luò)傳輸?shù)难舆t等問(wèn)題。對(duì)于能源非常有限的節(jié)點(diǎn)，如何延長(zhǎng)無(wú)線傳感器網(wǎng)絡(luò)的生命期是一個(gè)很重要的問(wèn)題。在無(wú)線傳感器網(wǎng)絡(luò)中，無(wú)線通信是能源的主要消耗者，無(wú)線通信主要是數(shù)據(jù)包的轉(zhuǎn)發(fā)，減少數(shù)據(jù)包的轉(zhuǎn)發(fā)次數(shù)，合理分配節(jié)點(diǎn)發(fā)送數(shù)據(jù)包的大小，有效利用節(jié)點(diǎn)轉(zhuǎn)發(fā)的數(shù)據(jù)包不但可以減少無(wú)線傳感器網(wǎng)絡(luò)的能量消耗，而且還可以保證在突發(fā)情況下保證網(wǎng)絡(luò)的暢通，降低災(zāi)害事件的發(fā)生。因此，節(jié)點(diǎn)擁塞避免是保證無(wú)線傳感器網(wǎng)絡(luò)正常傳輸?shù)囊粋€(gè)關(guān)鍵手段。
    近年來(lái)，WSN中的擁塞問(wèn)題日益引起了學(xué)術(shù)界的廣泛關(guān)注。研究人員逐步提出了多種針對(duì)WSN自身特點(diǎn)的控制策略(如CODA，ESRT，F(xiàn)usion等)。這些控制算法采用了不同的機(jī)制有效地減輕擁塞，是一種被動(dòng)的方式，可能導(dǎo)致節(jié)點(diǎn)數(shù)據(jù)的重發(fā)，且一般不能完全消除節(jié)點(diǎn)擁塞現(xiàn)象。
    現(xiàn)有無(wú)線傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)擁塞控制機(jī)制都是在節(jié)點(diǎn)發(fā)生擁塞時(shí)才采取一定的擁塞控制措施。但是，無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)大規(guī)模密集部署，在突發(fā)數(shù)據(jù)流引發(fā)擁塞后，再采用擁塞控制措施也不一定可以完全避免節(jié)點(diǎn)擁塞，很有可能導(dǎo)致災(zāi)難性的后果發(fā)生。因此，在本文中，提出了基于節(jié)點(diǎn)相對(duì)信息熵的擁塞避免機(jī)制，該擁塞避免機(jī)制是基于事件的有效信息量，真正體現(xiàn)無(wú)線傳感器網(wǎng)絡(luò)以事件為中心的特點(diǎn)。

1 基于信息熵的節(jié)點(diǎn)擁塞避免策略
    節(jié)點(diǎn)擁塞避免的重要問(wèn)題是按一定的策略，為網(wǎng)絡(luò)資源均衡合理地分配數(shù)據(jù)窗的大小。在無(wú)線傳感器網(wǎng)絡(luò)中，由于節(jié)點(diǎn)大規(guī)模部署，若兩個(gè)節(jié)點(diǎn)位于各自的通信半徑內(nèi)，它們可以直接通信。節(jié)點(diǎn)響應(yīng)監(jiān)測(cè)區(qū)域內(nèi)的事件或周期性地產(chǎn)生數(shù)據(jù)并發(fā)送至基站。如圖1所示，對(duì)于相同的感知區(qū)域，把感知到的數(shù)據(jù)轉(zhuǎn)發(fā)到下游節(jié)點(diǎn)，其下游節(jié)點(diǎn)不斷把數(shù)據(jù)再轉(zhuǎn)發(fā)到自身的下游節(jié)點(diǎn)，這樣不斷地進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)，最后可能導(dǎo)致下游的某個(gè)節(jié)點(diǎn)產(chǎn)生擁塞。顯然，對(duì)于大規(guī)模部署和處理緊急事件的無(wú)線傳感器網(wǎng)絡(luò)來(lái)講，擁塞不僅嚴(yán)重浪費(fèi)了節(jié)點(diǎn)能量還降低了轉(zhuǎn)發(fā)效率，而且還可能導(dǎo)致不可預(yù)料的事件發(fā)生。

1．1 WSN節(jié)點(diǎn)網(wǎng)絡(luò)模型
    WSN由分布在各個(gè)地方的傳感器節(jié)點(diǎn)通過(guò)自組織方式所形成的網(wǎng)絡(luò)模型。在該模型中，傳感器節(jié)點(diǎn)采集數(shù)據(jù)，通過(guò)無(wú)線傳感器網(wǎng)絡(luò)傳遞到基站，然后再傳遞給檢測(cè)中心。在這里假設(shè)每一個(gè)傳感器節(jié)點(diǎn)都有直接或間接與基站通信的能力，則節(jié)點(diǎn)會(huì)響應(yīng)監(jiān)測(cè)區(qū)域內(nèi)的事件或周期性地產(chǎn)生數(shù)據(jù)并發(fā)送到基站。
    假設(shè)N個(gè)傳感器節(jié)點(diǎn)按相對(duì)均勻的隨機(jī)高密度部署在一個(gè)監(jiān)測(cè)區(qū)域內(nèi)，具有以下性質(zhì)：
    (1)N個(gè)傳感器節(jié)點(diǎn)被隨機(jī)部署在監(jiān)測(cè)區(qū)域，基站不受能源限制，且位于一個(gè)區(qū)域的邊界上，其他傳感器節(jié)點(diǎn)為電池驅(qū)動(dòng)；
    (2)所有節(jié)點(diǎn)都為靜止節(jié)點(diǎn)，且各節(jié)點(diǎn)的軟硬件同構(gòu)，通信頻率相同；
    (3)每個(gè)節(jié)點(diǎn)采用全向天線，節(jié)點(diǎn)之間為雙向鏈路即A節(jié)點(diǎn)能和B節(jié)點(diǎn)通信，B節(jié)點(diǎn)也能和A節(jié)點(diǎn)通信，節(jié)點(diǎn)的通信范圍有限且通信半徑保持為R；
     (4)WSN的信道質(zhì)量可靠且傳輸?shù)恼`碼率基本可以忽略，其路由機(jī)制保持相對(duì)靜止，不會(huì)出現(xiàn)很大范圍的路由變化。
1．2 WSN中信息熵的數(shù)學(xué)定義
    在此基于WSN的網(wǎng)絡(luò)模型和信息論，給出WSN節(jié)點(diǎn)的信息熵的數(shù)學(xué)定義。
    定義1：節(jié)點(diǎn)信息熵：根據(jù)香農(nóng)的定義，自信息的數(shù)學(xué)期望為信息熵，因此節(jié)點(diǎn)信息熵表示節(jié)點(diǎn)N每發(fā)送一個(gè)數(shù)據(jù)包所提供的平均信息量：
   
    式中：q表示ai(i=1，2，…，q-1，q)的取值有q種可能性；P(ai)為字符ai出現(xiàn)的概率，節(jié)點(diǎn)信息熵H(X)表征了傳感器節(jié)點(diǎn)整體的統(tǒng)計(jì)特征，是總體平均不確定性的量度(單位：比特／數(shù)據(jù)包)。式(1)中的單位取決于對(duì)數(shù)函數(shù)的底數(shù)。本文中，取對(duì)數(shù)函數(shù)底數(shù)為2，即表示每個(gè)數(shù)據(jù)包含有1比特的信息量。
    在無(wú)線傳感器網(wǎng)絡(luò)中，節(jié)點(diǎn)感知到的數(shù)據(jù)既存在一定的差異又有一定的冗余，為了表征節(jié)點(diǎn)之間的這種關(guān)系，下面引入了節(jié)點(diǎn)相對(duì)信息熵。
    定義2：節(jié)點(diǎn)相對(duì)信息熵：假設(shè)P和Q是兩個(gè)概率分布函數(shù)，則定義P相對(duì)于Q的信息距離即節(jié)點(diǎn)相對(duì)信息熵為：
   
    式中：Pi和Qi為一個(gè)字符在節(jié)點(diǎn)中所出現(xiàn)的概率。
    節(jié)點(diǎn)相對(duì)信息熵可用于計(jì)算任意兩節(jié)點(diǎn)之間節(jié)點(diǎn)信息熵的差異性的大小。它的物理意義是兩組概率分布之間的差異性程度，因而對(duì)于兩組不同的概率分布P和Q，計(jì)算其節(jié)點(diǎn)相對(duì)信息熵D(P‖Q)，如果這個(gè)值越小，表明兩組概率分布越接近，這兩個(gè)節(jié)點(diǎn)之間的數(shù)據(jù)相似程度越大，則節(jié)點(diǎn)P就可以減少向節(jié)點(diǎn)Q發(fā)送數(shù)據(jù)包以保證網(wǎng)絡(luò)的暢通。對(duì)于極限情況，當(dāng)D(P‖Q)=0時(shí)，表示兩組概率分布完全相等，則這兩個(gè)節(jié)點(diǎn)之間的數(shù)據(jù)幾乎一樣，此時(shí)，節(jié)點(diǎn)P可以暫停向節(jié)點(diǎn)Q發(fā)送數(shù)據(jù)包。
1．3 基于節(jié)點(diǎn)信息熵的擁塞避免策略
    在一種路由協(xié)議機(jī)制下，若一個(gè)數(shù)據(jù)包從節(jié)點(diǎn)u發(fā)送至鄰居節(jié)點(diǎn)d，則稱u是d的上游節(jié)點(diǎn)，d是u的下游節(jié)點(diǎn)。在本文的網(wǎng)絡(luò)模型中，總是假設(shè)路由機(jī)制是靜態(tài)的或是很少進(jìn)行更新的，因此可知每個(gè)下游節(jié)點(diǎn)d總是可以知道有多少個(gè)上游節(jié)點(diǎn)u。按照上述基本假設(shè)，本文提出的擁塞避免策略過(guò)程如圖2所示。

1．4 算法的分析與實(shí)現(xiàn)
    在這里以雙重身份節(jié)點(diǎn)m(節(jié)點(diǎn)m既可以看作下游節(jié)點(diǎn)，也可以看作上游節(jié)點(diǎn))作為主要考慮節(jié)點(diǎn)，首先當(dāng)節(jié)點(diǎn)m作為上游節(jié)點(diǎn)時(shí)，向其自己的上游節(jié)點(diǎn)發(fā)送消息<req>，然后根據(jù)上游節(jié)點(diǎn)集反饋回來(lái)的消息<req>來(lái)計(jì)算節(jié)點(diǎn)相對(duì)信息熵的大小，根據(jù)計(jì)算出來(lái)的節(jié)點(diǎn)相對(duì)信息熵的大小來(lái)決定其分配的發(fā)送數(shù)據(jù)窗的大小。其中消息<req>主要包含發(fā)送節(jié)點(diǎn)的id、各數(shù)據(jù)包的信息量大小以及統(tǒng)計(jì)特性等信息。具體的擁塞避免算法實(shí)現(xiàn)過(guò)程如下：
    (1)如果節(jié)點(diǎn)m發(fā)送數(shù)據(jù)窗SDWm>0且當(dāng)前信道可用，則節(jié)點(diǎn)m根據(jù)其收到的下游節(jié)點(diǎn)發(fā)送的廣播消息<LMS>來(lái)決定發(fā)送自己的數(shù)據(jù)窗大??；
    (2)否則節(jié)點(diǎn)m發(fā)送數(shù)據(jù)窗SDWm=0，然后向其上游節(jié)點(diǎn)集發(fā)送消息<req>；
    (3)如果僅作為上游節(jié)點(diǎn)u的發(fā)送數(shù)據(jù)窗SDWm>0，則上游節(jié)點(diǎn)u退出上游節(jié)點(diǎn)集，此時(shí)上游節(jié)點(diǎn)u不響應(yīng)下游節(jié)點(diǎn)d發(fā)送的<req>，也不發(fā)送消息<req>；
    (4)如果僅作為上游節(jié)點(diǎn)u發(fā)送數(shù)據(jù)窗SDWm=0，上游節(jié)點(diǎn)集則向下游節(jié)點(diǎn)發(fā)送消息(req>；
    (5)下游節(jié)點(diǎn)m收到消息<req>開(kāi)始計(jì)算節(jié)點(diǎn)相對(duì)信息熵的大??；
    (6)根據(jù)計(jì)算得到節(jié)點(diǎn)相對(duì)信息熵的大小向上游節(jié)點(diǎn)集廣播消息<LMS>，通知上游節(jié)點(diǎn)u各自發(fā)送數(shù)據(jù)窗的大小，然后上游節(jié)點(diǎn)u根據(jù)收到的發(fā)送數(shù)據(jù)窗的大小來(lái)決定向下游節(jié)點(diǎn)發(fā)送一定數(shù)量的數(shù)據(jù)包，其中廣播消息<LMS>主要包括發(fā)送節(jié)點(diǎn)id及相應(yīng)發(fā)送數(shù)據(jù)窗的大小，且各發(fā)送數(shù)據(jù)包的大小之和小于本地可用緩沖區(qū)間。
    在上述過(guò)程中，若上游節(jié)點(diǎn)u當(dāng)前的發(fā)生數(shù)據(jù)窗大于0，則不響應(yīng)下游節(jié)點(diǎn)d發(fā)送的<req>，也不發(fā)送消息<req>，此時(shí)下游節(jié)點(diǎn)d不為上游節(jié)點(diǎn)u重新分配發(fā)送數(shù)據(jù)窗；若上游節(jié)點(diǎn)u完成了當(dāng)前的發(fā)生數(shù)據(jù)窗，則等待下游節(jié)點(diǎn)d發(fā)送下一個(gè)消息<req>。因此每個(gè)上游節(jié)點(diǎn)只有在收到消息<LMS>和之后的<req>之間發(fā)送數(shù)據(jù)包，可得知下游節(jié)點(diǎn)d處不會(huì)產(chǎn)生數(shù)據(jù)擁塞，整個(gè)網(wǎng)絡(luò)的節(jié)點(diǎn)擁塞因此而避免發(fā)生。

2 實(shí)驗(yàn)仿真
    為了驗(yàn)證本文所提出的避免節(jié)點(diǎn)擁塞機(jī)制的性能，選取經(jīng)典的CODA算法作比較?，F(xiàn)假設(shè)本文的仿真實(shí)驗(yàn)環(huán)境設(shè)置如下：
    (1)選取200個(gè)節(jié)點(diǎn)隨機(jī)部署在600×600的正方形區(qū)域內(nèi)，基站選擇在該區(qū)域邊界上；
    (2)節(jié)點(diǎn)的位置是固定的，且節(jié)點(diǎn)之間的通信半徑R=50，網(wǎng)絡(luò)帶寬設(shè)置為1 Mb／s；
    (3)信道質(zhì)量相對(duì)可靠，可忽略信道對(duì)誤碼率的影響，源節(jié)點(diǎn)產(chǎn)生的數(shù)據(jù)包大小相同，且報(bào)文的產(chǎn)生率為每單位時(shí)間10個(gè)數(shù)據(jù)包，節(jié)點(diǎn)可用最大緩沖區(qū)間為15個(gè)數(shù)據(jù)包。
    圖3描述了仿真過(guò)程中的網(wǎng)絡(luò)傳輸延遲。從圖中可以看出，CODA下的網(wǎng)絡(luò)傳輸延遲(每個(gè)到達(dá)基站的數(shù)據(jù)包在網(wǎng)絡(luò)中停留的時(shí)間)得到了一定的控制，而本文由于采用了基于發(fā)送數(shù)據(jù)窗的擁塞避免機(jī)制，降低了數(shù)據(jù)包在緩沖區(qū)內(nèi)的平均等待時(shí)間，減少了在網(wǎng)絡(luò)中的傳輸延遲。

    圖4表示了對(duì)網(wǎng)絡(luò)平均丟包率的比較。由于仿真環(huán)境假設(shè)信道質(zhì)量相對(duì)可靠，不會(huì)對(duì)網(wǎng)絡(luò)平均丟包率造成影響，因此，這里的數(shù)據(jù)包的丟失主要是由網(wǎng)絡(luò)的擁塞引起的。從圖中可以看出，CODA的網(wǎng)絡(luò)平均丟包率比本文的平均丟包率高。由于CODA采取了調(diào)節(jié)局部擁塞的節(jié)點(diǎn)，則在第120 s左右網(wǎng)絡(luò)平均丟包率趨于穩(wěn)定，網(wǎng)絡(luò)平均丟包率幾乎為0，但并不能保證在有突發(fā)數(shù)據(jù)流出現(xiàn)時(shí)隨著時(shí)間的推移還會(huì)出現(xiàn)網(wǎng)絡(luò)平均丟包率增大的現(xiàn)象。而本文的算法完全是采用的節(jié)點(diǎn)避免策略，因此在整個(gè)網(wǎng)絡(luò)生命周期內(nèi)，網(wǎng)絡(luò)的平均丟包率幾乎為0。

    圖5主要從無(wú)線傳感器網(wǎng)絡(luò)的能耗上進(jìn)行比較。由于CODA下的數(shù)據(jù)包傳輸跳數(shù)較少，進(jìn)而轉(zhuǎn)發(fā)數(shù)據(jù)包的次數(shù)也會(huì)減少，所以CODA的能耗相對(duì)較低一些。本文的算法雖然增加了傳輸跳數(shù)和節(jié)點(diǎn)之間的通信次數(shù)，但卻減少了由于沖突和擁塞帶來(lái)的能量浪費(fèi)，進(jìn)而有效地提高了能源的利用率。從圖5中可以看出，本文的算法比CODA的能量消耗相對(duì)多些，但這對(duì)于處理突發(fā)的緊急事件卻起著重要的作用，這樣即使多消耗了
一點(diǎn)能量，卻可以避免災(zāi)難性后果的發(fā)生。

3 結(jié)語(yǔ)
    本文在現(xiàn)有節(jié)點(diǎn)擁塞控制的基礎(chǔ)上提出了基于信息熵的節(jié)點(diǎn)擁塞避免機(jī)制。仿真測(cè)試表明，該算法更適合于突發(fā)情況下的無(wú)線傳感器網(wǎng)絡(luò)的特點(diǎn)。算法使用的基于信息熵的擁塞避免策略，可以有效地避免節(jié)點(diǎn)產(chǎn)生擁塞，從而減少了網(wǎng)絡(luò)的平均丟包率，降低了網(wǎng)絡(luò)中的傳輸延遲，這對(duì)于處理突發(fā)緊急的事件是非常重要的，由于節(jié)點(diǎn)不需要時(shí)刻監(jiān)測(cè)信道狀態(tài)，因此只有在有突發(fā)事件發(fā)生時(shí)，才會(huì)消耗大量能量?？偟膩?lái)說(shuō)，本文的算法是比較合理的。