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

張莉華，曹 斌

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

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

然而，傳感節點屬微型節點，它對數據處理能力是有限的，節點緩存容量有限。此外，在多數應用環境下，傳感節點數是非常多。當這些節點需要傳輸的數據包數超過緩存容量時，就會導致網絡擁塞[3]。而傳感節點數越多，網絡擁塞越嚴重。這勢必影響網絡的服務質量(Quality of Service,QoS),如吞吐量、時延、數據包丟失率。因此，控制網絡擁塞成為WSNs的一項關鍵技術。

文獻[4]引用仿生(bio-inspired)擁塞控制策略。通過平衡節點使用資源率或控制節點產生流量的速度，降低網絡擁塞概率。然而，該策略并沒有強烈節點占用資源的公平性問題，即并非所有傳感節點均有相同的機會去傳輸它的數據包。

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

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

最終，通過引用C-LV和PSO兩個算法，BICC算法實現兩個目標：控制流量，避免擁塞；最小化端到端時延。

1 BICC算法

BICC算法先利用C-LV優化節點的流量產生率，使各節點能夠公平地、無擁塞競爭資源。然后，利用粒子群優化PSO算法優化C-LV模型參數，降低流量的傳輸時延，算法框圖如圖1所示。

圖1 BICC算法框圖

1.1 C-LV概述

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

C-LV模型描述了物種競爭資源的關系，如式(1)所示：

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

(1)

物種競爭資源的最終結果不外乎兩種：所有物種共同分享資源，達到一種平衡;只有一個物種存在，其他物種滅絕。顯然，第一種結果是最優的穩定狀態，本文將此稱最穩定狀態。

1.2 應用于WSNs的C-LV

將C-LV應用于WSNs的流量控制，在不產生網絡擁塞的前提下，使各節點均能公平接入網絡，接入后再傳輸數據。即達到C-LV模式第一種結果。

在WSNs中，每個節點需要將自己所感測的數據傳輸至信宿。而信宿具有有限的緩存區域。當多個節點同時傳輸感測數據，或者所形成的數據流量超過信宿的緩存區域，則就形成數據丟失。因此，信宿的緩存區域是各數據流所競爭的資源。

圖2為系統模型。系統內有n個傳感節點，每個節點需要向信宿傳輸自己的數據流。將C-LV應用于WSNs后，物種、群體尺寸、競爭和資源的對應關系，如圖3所示。將傳感節點所需傳輸的流量看成物種，這些物種競爭網絡資源。而流量的字節數表示物種的群體尺寸。

圖2 系統模型

圖3 應用于WSNs的C-LV模型

如圖2所示，每個節點向信宿發送數據包(流量)。將每個節點看成競爭物種。且將信宿的緩沖容量看成每個物種的攜帶容量。而提出BICC算法的目的就是控制每個節點產生流量率，即動態調整流量率。

回顧到式(1)，其反映物種競爭資源的關系。將C-LV模型應用于WSNs后，仍可構建等式(1)?？紤]WSNs的網絡特性，可設定以下約束條件：

首先，每個流量具有相同的攜帶容量，即每條流量的數據包尺寸相等：

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

(2)

由于所有傳感節點為同構節點，彼此影響相同。因此，滿足式(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條流量的字節數。若是單位時間所傳輸的字節數，則其反映了流量的傳輸率。

將C-LV模型應用于WSNs的目的在于使所有節點能夠公平地競爭資源，而不是某單個節點獨占資源。即系統能達到最穩定狀態。依據特征值穩定理論：如果所有特征值均為非負數，則達到穩定。此外，僅當參數β>α>0時，才能獲取式(6)的全局非負的穩定狀態解，如式(7)所示：

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

(7)

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

(8)

如果α≥1，則不等式(8)永遠滿足。綜上所述，只要滿足式(9)，則可以保證各節點共存，達到最穩定狀態。

1.3 粒子群優化

粒子群優化PSO是依據動物生存法則而產生的仿生算法。多個粒子共同行走，但無發生碰撞。原因在于：每個粒子服從群體，調整自己的位置和速度。

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

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表示全局最優位置。而慣性權重ω為速度的擴展因子。常數c1、c2決定P、G的權重。而r1、r2為兩個隨機數，且它們服從[0,1]的隨機分布。

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

圖4 算法1設計圖

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

圖5 算法2設計圖

利用算法2產生目標函數f(α,β)，其中M表示抽樣的次數。盡管f(α,β)不能完全代表網絡的平均時延，但是它與網絡的平均時延呈線性關系。因此，最小化目標函數f(α,β)等同價于最小化平均時延。

2 性能仿真

2.1 仿真環境

利用NS3++軟件建立實驗平臺?？紤]星形拓撲網絡，如圖6所示。其中傳感節點數為20。信宿節點的緩存容量這30 KB。抽樣時間為1 s。同時引用基于CSMA的IEEE 802.11 MAC協議作為接入協議。最初，每個節點向信宿傳輸的速度為1 Kbps，隨后，BICC算法控制各節點的傳輸速率。

2.2 性能分析

提出BICC算法的主旨在于自適應地調整節點的傳輸速率。因此，重點分析節點的傳輸速率，檢測是否能調整節點傳輸速率。

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

圖6 星形的拓撲結構

圖7顯示了這4個階段的控制速率的情況。從圖7可知，節點的傳輸速率隨節點數逐步在變化。圖8將第1階段的傳輸速率圖進行了放大，其只顯示了第1階段5個傳感節點的傳輸速率。

圖7 基于BICC的流量控制

圖8 第1階段的傳輸速率

從圖8可知，5個傳感節點的傳輸速率接近6 Kbps，正好逼近于信宿的緩存容量30 KB。并且沒有任何擁塞出現。這些數據說明，提出的BICC算法能夠有效調整傳輸速率，并控制網絡無擁塞。

圖9顯示了第2階段10個傳感節點的傳輸速率。從圖9可知，BICC算法能夠有效地調整傳輸速率：在前100 s，5個傳感節點的傳輸速率約為5.5 Kbps，但當節點數增加至10個后，傳輸速率馬上調整至近3 Kbps。

圖9 10個傳感節點的傳輸速率

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

圖10 基于AIDM的流量控制

從圖10可知，AIDM算法所控制的傳輸速率波動大，這說明傳感節點在傳輸數據時，出現擁塞。對比圖5，不難發現，BICC算法能夠有效調整傳輸速率，并達到穩定。

3 結論

針對WSNs網絡擁塞問題，提出BICC算法進行擁塞控制。BICC算法引用C-LV模型解決WSNs的擁塞問題，進而維持節點間的公平。同時，利用PSO優化C-LV模型參數，進而使BICC算法能夠自適應應對節點數的增加。

仿真結果表明：提出的BICC算法能夠避免擁塞，維持高的數據傳輸速率，并使得節點的傳輸率達到最優的狀態。后期將BICC算法應用到真實的工業系統，并分析它的性能，這將是后期的工作方向。