基于網絡微積分的WSNs屬性界限研究

李 翠，巨永鋒

(1.長安大學電子與控制工程學院，陜西 西安710064;2.江西贛粵高速公路股份有限公司，江西南昌330025)

0 引言

由于無線傳感器節點的通信半徑有限，不能覆蓋整個網絡，數據通常需要經過多跳轉發才能抵達基站［1］。這使得WSNs的屬性界限變得復雜。WSNs屬性界限包括數據傳輸端到端延遲上界、節點緩沖區容量下界以及節點服務速率(即通信帶寬)下界等。這些屬性界限是配置WSNs相關功能參數(比如:節點分布密度、通信半徑、緩沖區大小以及通信帶寬等)的重要依據和提高網絡服務質量的重要內容。

目前，關于WSNs屬性界限方面的研究主要有2個研究方向:一個側重于路由算法的設計［2～5］，研究如何減小網絡時延，并尋找統計學意義上的時延界限;另一個則側重于利用網絡微積分計算WSNs屬性界限，并根據計算結果進行網絡配置［6～8］。文獻［6］結合鏈路吞吐量模型對無線自組網的端到端延遲上界進行了研究，但其結論僅適用于只在源節點有輸入數據流的串聯節點系統。文獻［7］利用網絡微積分建立了一個通用分析模式，用于求解WSNs屬性界限。該文獻最大的貢獻在于得出父節點到達曲線為各子節點到達曲線的函數這一結論。文獻［8］將文獻［7］的分析模式分別拓展到不同拓撲條件下的網絡，如不確定性拓撲、多匯聚點拓撲以及樹狀路由拓撲等。文獻［9］面向前饋(feed-forward)網絡，對流經同一節點不同數據流的服務曲線進行區別化分配，以求解更精確的延遲上界。

基于網絡微積分［10，11］，本文修正了流經節點的數據流輸出上界，推導出更精確的WSNs屬性界限，并通過數值分析對屬性界限進行比較。

1 網絡微積分相關概念

網絡微積分基于最小加代數理論，是一種新的可用于網絡建模和定量分析的數學工具，利用它可以分析網絡延遲、隊列緩沖區大小以及節點帶寬等一些網絡的基本屬性。網絡微積分主要包括到達曲線、服務曲線以及最小加代數下的卷積和反卷積等基本概念。其中，到達曲線用來描述一個數據流的輸入特性并對其加以約束;服務曲線則反映了節點轉發數據流的調度細節和服務能力，對數據流在流經節點時輸入行為和輸出行為之間的關系進行抽象。相關定義如下:

定義1 廣義增函數:對于?s≤1，若f(s)≤f(t)均成立，則稱 f為廣義增函數。

定義2 廣義增函數集合:若 F={f(t)|，f(t)=0，?t＜0;f(s)≤f(t)，t∈［0，+∞］}，則稱 F 為廣義增函數集合。

定義3 最小加卷積:對于?f，g∈F，函數f和g的最小加卷積運算為

定義4 最小加反卷積:對于?f，g∈F，函數f和g的最小加反卷積運算為

定義5 到達曲線:給定一個廣義增函數α∈F，若輸入流的累積函數R對任意時刻s和t均滿足

其中，0≤s≤t，則稱α是R的到達曲線。

定義6 服務曲線:給定一個廣義增函數β∈F，對于一個系統S和流經S的流，在輸入端和輸出端該流的累積函數分別為R和R*，當且僅當

其中，0≤s≤t，則稱β是S為數據流提供的服務曲線。

在已知數據流到達曲線α和服務曲線β的情況下，可以得出如下幾個定理:

定理1 積壓上界:假設到達曲線為α的數據流通過一個所提供服務曲線為β的系統S，那么，對任意時間t，系統S中積壓的數據滿足

定理2 延遲上界:假設到達曲線為α的數據流通過一個所提供服務曲線為β的系統S，那么，對任意時間t，數據流在S中的延遲滿足

定理3 輸出上界:假設到達曲線為α的數據流通過一個所提供服務曲線為β的系統S，那么，輸出上界為

定理4 假設系統S1和S2提供的服務曲線分別為β1和β2，系統S1和系統S2串聯后提供的總服務曲線為β，則 β =β1?β2。

2 流量模型與屬性界限

2.1 感知數據到達曲線與服務曲線

假設傳感器節點均為同構，監測區域具有比較平均的數據突發率，每個節點均能感知并接收到監測數據，從平均的角度看，可以認為不同的節點具有相同的監測數據量。監測數據輸入對應節點時的到達曲線滿足漏桶管制(leaky bucket regulated)［8］，到達曲線表示為

式中 rs和bs分別為每個節點感知范圍內監測數據的平均速率和突發數據大小，bs又稱為漏桶容量。

因節點是同構的，故假定每個節點均具有相同的服務能力，其基于速率—延遲的服務曲線為

式中 Rs為節點服務速率，且Rs≥ri;Ts為數據在節點緩沖區中的最大調度延遲;(x)+=max(0，x)。

2.2 輸出上界

考察某FIFO節點(輸入輸出節點)輸入—輸出數據流的關系。在時刻t，輸入端到達曲線為α(t)，輸出端實際輸出曲線為α'(t)，輸出端輸出上界為α*(t)。參考文獻對數據流輸出上界的求解均是基于定理3公式(7)，則滿足式(8)流量約束條件的數據流輸出上界為α*(t)=α(t)+rT。該輸出上界與節點調度延遲T相關，明顯偏大。假定數據流經過節點的實際延遲為d，由于節點服務速率足夠大，故節點中積壓數據實際應為rd，輸出端實際輸出曲線應為α'(t)=α(t)－rd≤α(t)。考慮到延遲d為變量，存在不確定性，因此，輸出上界可取為

上式表明:在同一時刻t，輸出端實際輸出的流量不會高于輸入端實際輸入的流量，物理意義明確。和參考文獻采用的輸出上界相比，式(10)更精確且更符合實際情況。

2.3 屬性界限

在WSNs中，傳感器節點的通信半徑有限，傳輸范圍不能覆蓋整個網絡，數據通常需要通過多跳路由轉發才能抵達基站。因此，網絡中數據流呈現不均勻狀態，數據流往基站方向匯聚，節點越靠近基站，則需要服務的數據流越多。對于網絡中的某一傳輸路徑，可以將其作為一個只接收數據流匯聚的系統，系統內任意一跳節點的輸出數據全部往下一跳父節點傳送。這個假定符合WSNs中數據流往基站匯聚的規律。

對于節點i，輸入數據流為匯聚流，該匯聚流包括節點i自身感應數據流和子節點轉發過來的數據流，如圖1所示，其到達曲線如下式所示

式中 Ni，child_all是以節點i為必經路由的所有節點數量，即流經節點i的所有轉發感應數據流的數量。

圖1 流經節點i的匯聚數據流Fig 1 Aggregate data flows traversing node i

對于某總跳數為H的傳輸路徑，源節點到基站的端到端延遲上界為各跳最大延遲之和，如下式

對于同構WSNs，端到端延遲上界應為

由式(14)可知，傳輸路徑總跳數H越大，匯聚至該傳輸路徑的數據流越多，則端到端延遲上界越大。

由式(5)和式(12)得到節點i緩沖區容量下界(即積壓上界)為

若式(16)不能滿足，則網絡通信繁忙時節點緩沖區可能溢出，造成丟包。由式(16)可知，匯聚至節點i的數據流越多，積壓上界越大。

為保證數據傳輸通暢，要求節點服務速率下界滿足

若式(17)不能滿足，則可能引起通信阻塞，從而造成數據丟失和網絡延遲增大。

3 實驗分析

以圖2所示WSNs拓撲結構［7］為例進行數值分析。監測區域為8 d×8 d的正方形，均勻布置80個傳感器，每個傳感器節點通信半徑為理想的。基站位于方形區域正中。在第一個節點死亡之前，節點總是以最短路徑進行數據傳輸。部分傳輸路徑如圖2所示。假定為同構WSNs，rs=0.1 kbps，bs=0.2 kb，Rs=1 Mbps，Ts=0.1 s，服務速率和節點緩沖區足夠大。WSNs屬性界限如表1和表2所示。

圖2 WSNs拓撲示意圖Fig 2 Diagram of WSNs topology

表1 端到端延遲上界Tab 1 End-to-end delay upper bound

表2 積壓上界與服務速率下界Tab 2 Backlog upper bound and service rate lower bound

由表1和表2可知，方法1求得的節點延遲上界和積壓上界比方法2的要小，而服務速率下界相同。隨著網絡跳數的增加與節點梯度的減小(即離基站更近)，節點延遲上界和積壓上界差異越來越大。這種差異來源于2種方法采用了不同的數據流輸出函數上界。數值分析結果表明:網絡規模越大，按本文屬性界限進行網絡配置能節約更多資源。

4 結論

本文對流經網絡節點的數據流輸出函數上界進行了改進，使其更符合物理意義，并由此推導出更精確的WSNs屬性界限。與現有文獻屬性界限相比，本文求得的延遲上界和積壓上界表達式更簡單和精確，但服務速率下界是相同的。本文所得WSNs屬性界限是WSNs網絡配置的重要依據。數值分析結果表明:網絡規模越大，按本文屬性界限進行網絡配置能節約更多資源。

［1］hajela R，Garimella R M，Sabnani D.LCSD:Leveling clustering and sectoring with dissemination nodes to perform energy efficient routing in mobile cognitive wireless sensor networks［C］∥2010 International Conference on Computational Intelligence and Communication Networks:IEEE Computer Society，2010:177－182.

［2］Pothuri P K，Sarangan V，Thomas J P.Delay-guaranteed，energyefficient routing in wireless sensor networks through topology control［C］∥ Proceedings of the 2006 IEEE International Conference，Piscataway，NJ，USA，IEEE，2006:35－41.

［3］Ahmed A A，Fisal N.A real-time routing protocol with load distribution in wireless sensor networks［J］.Computer Communications，2008，31(14):3190－3203.

［4］Xu Yingsheng，Ren Fengyuan，He Tao，et al.Building a potential field to provide real-time transmission in wireless sensor networks［C］∥Proceedings of the 13th ACM International Conference on Modeling，Analysis and Simulation of Wireless and Mobile Systems，New York，USA，ACM，2010:403－410.

［5］梁慶偉，姚道遠，鞏思亮.一種保障時延能量高效的無線傳感器網絡路由協議［J］.西安交通大學學報，2012，46(6):48－52.

［6］李慶華，陳志剛，黃國盛，等，基于網絡演算的無線自組網端到端延遲上界研究［J］.系統仿真學報，2009，21(8):2248－2251.

［7］Schmitt JB，Roedig U.Sensor network calculus—A framework for worst case analysis［C］∥Proceedings of the International Conference on Distributed Computing in Sensor Systems(DCOSS05)，USA，2005:141－154.

［8］Koubaa A，Alves M，Tovar E.Modeling and worst-case dimensioning of cluster-tree wireless sensor networks［C/OL］∥Proceedings of the 27th IEEE Real-Time Systems Symposium(RTSS06’)，Rio de Janeiro，Brazil，2006.［2012—07—01］.http://citeseerx.ist.psu.edu.

［9］Kiefer A，Gollan N，Schmitt H B.Searching for tight performance bounds in feed-forward networks［C］∥Measurement，Modeling，and Evaluation of Computing Systems and Dependability and Fault Tolerance，Berlin，Germany:Springer，2010:227－241.

［10］Chang Chengshang，Cruz R L，Boudec J Y L，et al.A min-plus system theory for constrained traffic regulation and dynamic service guarantees［J］.IEEE/ACM Trans on Networking，2002，10(6):805－817.

［11］高文宇，陳喬松，王建新.網絡微積分學研究［J］.微電子學與計算機，2004，21(11):76－80.