WSNs中基于仿生模型的擁塞控制算法

張莉華，曹 斌

(黃淮學(xué)院 信息工程學(xué)院， 河南 駐馬店 463000)

隨著短距離通信技術(shù)的快速發(fā)展，物聯(lián)網(wǎng)相關(guān)技術(shù)已成為研究人員關(guān)注的焦點(diǎn)。數(shù)據(jù)采集是物聯(lián)網(wǎng)應(yīng)用的關(guān)鍵階段。微型的、能量受限的具有數(shù)據(jù)感采集能力的傳感節(jié)點(diǎn)組成的無線傳感網(wǎng)絡(luò) (Wireless Sensor Networks，WSNs)[1-2]已在醫(yī)療、環(huán)境監(jiān)測(cè)、軍事等領(lǐng)域得到廣泛應(yīng)用。這些傳感節(jié)點(diǎn)的主要任務(wù)就是感測(cè)數(shù)據(jù)，然后以單跳或多跳方式傳輸至信宿。

然而，傳感節(jié)點(diǎn)屬微型節(jié)點(diǎn)，它對(duì)數(shù)據(jù)處理能力是有限的，節(jié)點(diǎn)緩存容量有限。此外，在多數(shù)應(yīng)用環(huán)境下，傳感節(jié)點(diǎn)數(shù)是非常多。當(dāng)這些節(jié)點(diǎn)需要傳輸?shù)臄?shù)據(jù)包數(shù)超過緩存容量時(shí)，就會(huì)導(dǎo)致網(wǎng)絡(luò)擁塞[3]。而傳感節(jié)點(diǎn)數(shù)越多，網(wǎng)絡(luò)擁塞越嚴(yán)重。這勢(shì)必影響網(wǎng)絡(luò)的服務(wù)質(zhì)量(Quality of Service,QoS),如吞吐量、時(shí)延、數(shù)據(jù)包丟失率。因此，控制網(wǎng)絡(luò)擁塞成為WSNs的一項(xiàng)關(guān)鍵技術(shù)。

文獻(xiàn)[4]引用仿生(bio-inspired)擁塞控制策略。通過平衡節(jié)點(diǎn)使用資源率或控制節(jié)點(diǎn)產(chǎn)生流量的速度，降低網(wǎng)絡(luò)擁塞概率。然而，該策略并沒有強(qiáng)烈節(jié)點(diǎn)占用資源的公平性問題，即并非所有傳感節(jié)點(diǎn)均有相同的機(jī)會(huì)去傳輸它的數(shù)據(jù)包。

為此，提出基于仿生模型的擁塞控制(Bio-inspired based Congestion Control,BICC)算法。BICC算法引用兩個(gè)仿生算法控制WSNs的擁塞問題。首先，引用競(jìng)爭(zhēng)洛特卡-伏爾特拉(Competitive Lotka-Volterra,C-LV)模型[5]降低網(wǎng)絡(luò)擁塞。C-LV模型維持所有節(jié)點(diǎn)的公平性，并控制節(jié)點(diǎn)產(chǎn)生數(shù)據(jù)流的速度，進(jìn)而預(yù)防擁塞。引用C-LV仿生算法的目的在于：自適應(yīng)地控制產(chǎn)生數(shù)據(jù)流的速度，進(jìn)而避免網(wǎng)絡(luò)擁塞。C-LV模型通過合適地選擇參數(shù)，維持免擁塞地傳輸流量。然而，選擇參數(shù)是非常耗時(shí)，并且當(dāng)節(jié)點(diǎn)數(shù)較多時(shí)，選擇合適參數(shù)是不太可能。

據(jù)此，引用第二個(gè)仿生算法，粒子群優(yōu)化(Particle Swarm Optimization,PSO)[6-7]優(yōu)化C-LV參數(shù)。C-LV模型中有一重要的參數(shù)必須慎重選擇。而PSO算法可以完成這個(gè)任務(wù)。此外，為了避免擁塞和維持公平，PSO通過優(yōu)化節(jié)點(diǎn)傳輸率，提高C-LV模型的性能。同時(shí)，降低端到端傳輸時(shí)延也是運(yùn)行PSO算法的目的。

最終，通過引用C-LV和PSO兩個(gè)算法，BICC算法實(shí)現(xiàn)兩個(gè)目標(biāo)：控制流量，避免擁塞；最小化端到端時(shí)延。

1 BICC算法

BICC算法先利用C-LV優(yōu)化節(jié)點(diǎn)的流量產(chǎn)生率，使各節(jié)點(diǎn)能夠公平地、無擁塞競(jìng)爭(zhēng)資源。然后，利用粒子群優(yōu)化PSO算法優(yōu)化C-LV模型參數(shù)，降低流量的傳輸時(shí)延，算法框圖如圖1所示。

圖1 BICC算法框圖

1.1 C-LV概述

假定有n個(gè)物種，xi(t)表示在時(shí)刻t，物種i的群體尺寸(Population Size)。而ri表示在沒有其他競(jìng)爭(zhēng)物種下，物種i的內(nèi)在增長(zhǎng)率。而Ki表示物種i的最大群體尺寸。αij表示物種j的群體對(duì)物種i的生長(zhǎng)的影響。而αii表示物種i的群體對(duì)它自已的生長(zhǎng)的影響。

C-LV模型描述了物種競(jìng)爭(zhēng)資源的關(guān)系，如式(1)所示：

?i∈{1,2,3,…,n}

(1)

物種競(jìng)爭(zhēng)資源的最終結(jié)果不外乎兩種：所有物種共同分享資源，達(dá)到一種平衡;只有一個(gè)物種存在，其他物種滅絕。顯然，第一種結(jié)果是最優(yōu)的穩(wěn)定狀態(tài)，本文將此稱最穩(wěn)定狀態(tài)。

1.2 應(yīng)用于WSNs的C-LV

將C-LV應(yīng)用于WSNs的流量控制，在不產(chǎn)生網(wǎng)絡(luò)擁塞的前提下，使各節(jié)點(diǎn)均能公平接入網(wǎng)絡(luò)，接入后再傳輸數(shù)據(jù)。即達(dá)到C-LV模式第一種結(jié)果。

在WSNs中，每個(gè)節(jié)點(diǎn)需要將自己所感測(cè)的數(shù)據(jù)傳輸至信宿。而信宿具有有限的緩存區(qū)域。當(dāng)多個(gè)節(jié)點(diǎn)同時(shí)傳輸感測(cè)數(shù)據(jù)，或者所形成的數(shù)據(jù)流量超過信宿的緩存區(qū)域，則就形成數(shù)據(jù)丟失。因此，信宿的緩存區(qū)域是各數(shù)據(jù)流所競(jìng)爭(zhēng)的資源。

圖2為系統(tǒng)模型。系統(tǒng)內(nèi)有n個(gè)傳感節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)需要向信宿傳輸自己的數(shù)據(jù)流。將C-LV應(yīng)用于WSNs后，物種、群體尺寸、競(jìng)爭(zhēng)和資源的對(duì)應(yīng)關(guān)系，如圖3所示。將傳感節(jié)點(diǎn)所需傳輸?shù)牧髁靠闯晌锓N，這些物種競(jìng)爭(zhēng)網(wǎng)絡(luò)資源。而流量的字節(jié)數(shù)表示物種的群體尺寸。

圖2 系統(tǒng)模型

圖3 應(yīng)用于WSNs的C-LV模型

如圖2所示，每個(gè)節(jié)點(diǎn)向信宿發(fā)送數(shù)據(jù)包(流量)。將每個(gè)節(jié)點(diǎn)看成競(jìng)爭(zhēng)物種。且將信宿的緩沖容量看成每個(gè)物種的攜帶容量。而提出BICC算法的目的就是控制每個(gè)節(jié)點(diǎn)產(chǎn)生流量率，即動(dòng)態(tài)調(diào)整流量率。

回顧到式(1)，其反映物種競(jìng)爭(zhēng)資源的關(guān)系。將C-LV模型應(yīng)用于WSNs后，仍可構(gòu)建等式(1)?？紤]WSNs的網(wǎng)絡(luò)特性，可設(shè)定以下約束條件：

首先，每個(gè)流量具有相同的攜帶容量，即每條流量的數(shù)據(jù)包尺寸相等：

Ki=K,?i∈{1,2,3,…,n}

(2)

由于所有傳感節(jié)點(diǎn)為同構(gòu)節(jié)點(diǎn)，彼此影響相同。因此，滿足式(3):

αij=α,?i,j∈{1,2,3,…,n} andi≠j

(3)

且

αii=β,?i∈{1,2,3,…,n}

(4)

因此，將式(2)、式(3)、式(4)代入式(1)可得：

?i∈{1,2,3,…,n}

(5)

而式(5)的解可表示為

(6)

其中ω=K-αCi。式(6)表示第i條流量的字節(jié)數(shù)。若是單位時(shí)間所傳輸?shù)淖止?jié)數(shù)，則其反映了流量的傳輸率。

將C-LV模型應(yīng)用于WSNs的目的在于使所有節(jié)點(diǎn)能夠公平地競(jìng)爭(zhēng)資源，而不是某單個(gè)節(jié)點(diǎn)獨(dú)占資源。即系統(tǒng)能達(dá)到最穩(wěn)定狀態(tài)。依據(jù)特征值穩(wěn)定理論：如果所有特征值均為非負(fù)數(shù)，則達(dá)到穩(wěn)定。此外，僅當(dāng)參數(shù)β>α>0時(shí)，才能獲取式(6)的全局非負(fù)的穩(wěn)定狀態(tài)解，如式(7)所示：

?i∈{1,2,3,…,n}

(7)

α(n-1)+β≥norβ-α≥n(1-α)

(8)

如果α≥1，則不等式(8)永遠(yuǎn)滿足。綜上所述，只要滿足式(9)，則可以保證各節(jié)點(diǎn)共存，達(dá)到最穩(wěn)定狀態(tài)。

1.3 粒子群優(yōu)化

粒子群優(yōu)化PSO是依據(jù)動(dòng)物生存法則而產(chǎn)生的仿生算法。多個(gè)粒子共同行走，但無發(fā)生碰撞。原因在于：每個(gè)粒子服從群體，調(diào)整自己的位置和速度。

在PSO算法中，每個(gè)粒子代表一個(gè)優(yōu)化群體目標(biāo)的可行解。令f(x)表示目標(biāo)函數(shù)。用X=(x1,x2,…,xN)、V=(?1,?2,…,?N)分別表示粒子群個(gè)體位置矢量、速度矢量，其中N表示群體數(shù)。并且依據(jù)式(10)、式(11)進(jìn)行更新位置矢量和速度矢量：

X(t+1)=X(t)+V(t+1)

(10)

V(t+1)=ωV(t)+c1r1(P-X(t))+c2r2(G(t)-X(t))

(11)

其中P=(p1,p2,p3,…,pN)表示每個(gè)粒子個(gè)人最優(yōu)解，而G表示全局最優(yōu)位置。而慣性權(quán)重ω為速度的擴(kuò)展因子。常數(shù)c1、c2決定P、G的權(quán)重。而r1、r2為兩個(gè)隨機(jī)數(shù)，且它們服從[0,1]的隨機(jī)分布。

假定有N個(gè)粒子，每個(gè)粒子最大迭代次數(shù)為MaxIteration。每個(gè)粒子依據(jù)算法1進(jìn)行更新位置矢量和速度矢量。算法1如圖4所示。

圖4 算法1設(shè)計(jì)圖

引用PSO算法的目的在于：通過優(yōu)化參數(shù)α、β，降低平均時(shí)延。當(dāng)然，參數(shù)α、β必須滿足式(9)。實(shí)際上，式(9)規(guī)定了α、β下限值。算法2如圖5所示。

圖5 算法2設(shè)計(jì)圖

利用算法2產(chǎn)生目標(biāo)函數(shù)f(α,β)，其中M表示抽樣的次數(shù)。盡管f(α,β)不能完全代表網(wǎng)絡(luò)的平均時(shí)延，但是它與網(wǎng)絡(luò)的平均時(shí)延呈線性關(guān)系。因此，最小化目標(biāo)函數(shù)f(α,β)等同價(jià)于最小化平均時(shí)延。

2 性能仿真

2.1 仿真環(huán)境

利用NS3++軟件建立實(shí)驗(yàn)平臺(tái)?？紤]星形拓?fù)渚W(wǎng)絡(luò)，如圖6所示。其中傳感節(jié)點(diǎn)數(shù)為20。信宿節(jié)點(diǎn)的緩存容量這30 KB。抽樣時(shí)間為1 s。同時(shí)引用基于CSMA的IEEE 802.11 MAC協(xié)議作為接入?yún)f(xié)議。最初，每個(gè)節(jié)點(diǎn)向信宿傳輸?shù)乃俣葹? Kbps，隨后，BICC算法控制各節(jié)點(diǎn)的傳輸速率。

2.2 性能分析

提出BICC算法的主旨在于自適應(yīng)地調(diào)整節(jié)點(diǎn)的傳輸速率。因此，重點(diǎn)分析節(jié)點(diǎn)的傳輸速率，檢測(cè)是否能調(diào)整節(jié)點(diǎn)傳輸速率。

為了更好地分析BICC調(diào)整速率的性能，采用逐步增加節(jié)點(diǎn)數(shù)的方法。最初，先增加5個(gè)傳感節(jié)點(diǎn)(sensor1、sensor 2、sensor 3、sensor 4、 sensor 5)，100 s后，再增加5個(gè)傳感節(jié)點(diǎn)，直到添加了20個(gè)傳感節(jié)點(diǎn)。因此，20個(gè)傳感節(jié)點(diǎn)分了4段，為了簡(jiǎn)化描述，第1階段用Sensor Node 1表述；第2階段用Sensor Node 6表述；第3階段用Sensor Node 11表述；而第4階段用Sensor Node 16表述。

圖6 星形的拓?fù)浣Y(jié)構(gòu)

圖7顯示了這4個(gè)階段的控制速率的情況。從圖7可知，節(jié)點(diǎn)的傳輸速率隨節(jié)點(diǎn)數(shù)逐步在變化。圖8將第1階段的傳輸速率圖進(jìn)行了放大，其只顯示了第1階段5個(gè)傳感節(jié)點(diǎn)的傳輸速率。

圖7 基于BICC的流量控制

圖8 第1階段的傳輸速率

從圖8可知，5個(gè)傳感節(jié)點(diǎn)的傳輸速率接近6 Kbps，正好逼近于信宿的緩存容量30 KB。并且沒有任何擁塞出現(xiàn)。這些數(shù)據(jù)說明，提出的BICC算法能夠有效調(diào)整傳輸速率，并控制網(wǎng)絡(luò)無擁塞。

圖9顯示了第2階段10個(gè)傳感節(jié)點(diǎn)的傳輸速率。從圖9可知，BICC算法能夠有效地調(diào)整傳輸速率：在前100 s，5個(gè)傳感節(jié)點(diǎn)的傳輸速率約為5.5 Kbps，但當(dāng)節(jié)點(diǎn)數(shù)增加至10個(gè)后，傳輸速率馬上調(diào)整至近3 Kbps。

圖9 10個(gè)傳感節(jié)點(diǎn)的傳輸速率

最后，引用典型的流量控制算法，和式增加積式下降(Additive Increase Multiplication Decrease,AIMD)算法[8]與BICC算法進(jìn)行比較。圖10也顯示了20個(gè)傳感節(jié)點(diǎn)的傳輸速率情況。

圖10 基于AIDM的流量控制

從圖10可知，AIDM算法所控制的傳輸速率波動(dòng)大，這說明傳感節(jié)點(diǎn)在傳輸數(shù)據(jù)時(shí)，出現(xiàn)擁塞。對(duì)比圖5，不難發(fā)現(xiàn)，BICC算法能夠有效調(diào)整傳輸速率，并達(dá)到穩(wěn)定。

3 結(jié)論

針對(duì)WSNs網(wǎng)絡(luò)擁塞問題，提出BICC算法進(jìn)行擁塞控制。BICC算法引用C-LV模型解決WSNs的擁塞問題，進(jìn)而維持節(jié)點(diǎn)間的公平。同時(shí)，利用PSO優(yōu)化C-LV模型參數(shù)，進(jìn)而使BICC算法能夠自適應(yīng)應(yīng)對(duì)節(jié)點(diǎn)數(shù)的增加。

仿真結(jié)果表明：提出的BICC算法能夠避免擁塞，維持高的數(shù)據(jù)傳輸速率，并使得節(jié)點(diǎn)的傳輸率達(dá)到最優(yōu)的狀態(tài)。后期將BICC算法應(yīng)用到真實(shí)的工業(yè)系統(tǒng)，并分析它的性能，這將是后期的工作方向。