基于網(wǎng)絡(luò)微積分的WSNs屬性界限研究

李 翠，巨永鋒

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

0 引言

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

目前，關(guān)于WSNs屬性界限方面的研究主要有2個(gè)研究方向:一個(gè)側(cè)重于路由算法的設(shè)計(jì)［2～5］，研究如何減小網(wǎng)絡(luò)時(shí)延，并尋找統(tǒng)計(jì)學(xué)意義上的時(shí)延界限;另一個(gè)則側(cè)重于利用網(wǎng)絡(luò)微積分計(jì)算WSNs屬性界限，并根據(jù)計(jì)算結(jié)果進(jìn)行網(wǎng)絡(luò)配置［6～8］。文獻(xiàn)［6］結(jié)合鏈路吞吐量模型對無線自組網(wǎng)的端到端延遲上界進(jìn)行了研究，但其結(jié)論僅適用于只在源節(jié)點(diǎn)有輸入數(shù)據(jù)流的串聯(lián)節(jié)點(diǎn)系統(tǒng)。文獻(xiàn)［7］利用網(wǎng)絡(luò)微積分建立了一個(gè)通用分析模式，用于求解WSNs屬性界限。該文獻(xiàn)最大的貢獻(xiàn)在于得出父節(jié)點(diǎn)到達(dá)曲線為各子節(jié)點(diǎn)到達(dá)曲線的函數(shù)這一結(jié)論。文獻(xiàn)［8］將文獻(xiàn)［7］的分析模式分別拓展到不同拓?fù)錀l件下的網(wǎng)絡(luò)，如不確定性拓?fù)?、多匯聚點(diǎn)拓?fù)湟约皹錉盥酚赏負(fù)涞?。文獻(xiàn)［9］面向前饋(feed-forward)網(wǎng)絡(luò)，對流經(jīng)同一節(jié)點(diǎn)不同數(shù)據(jù)流的服務(wù)曲線進(jìn)行區(qū)別化分配，以求解更精確的延遲上界。

基于網(wǎng)絡(luò)微積分［10，11］，本文修正了流經(jīng)節(jié)點(diǎn)的數(shù)據(jù)流輸出上界，推導(dǎo)出更精確的WSNs屬性界限，并通過數(shù)值分析對屬性界限進(jìn)行比較。

1 網(wǎng)絡(luò)微積分相關(guān)概念

網(wǎng)絡(luò)微積分基于最小加代數(shù)理論，是一種新的可用于網(wǎng)絡(luò)建模和定量分析的數(shù)學(xué)工具，利用它可以分析網(wǎng)絡(luò)延遲、隊(duì)列緩沖區(qū)大小以及節(jié)點(diǎn)帶寬等一些網(wǎng)絡(luò)的基本屬性。網(wǎng)絡(luò)微積分主要包括到達(dá)曲線、服務(wù)曲線以及最小加代數(shù)下的卷積和反卷積等基本概念。其中，到達(dá)曲線用來描述一個(gè)數(shù)據(jù)流的輸入特性并對其加以約束;服務(wù)曲線則反映了節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)流的調(diào)度細(xì)節(jié)和服務(wù)能力，對數(shù)據(jù)流在流經(jīng)節(jié)點(diǎn)時(shí)輸入行為和輸出行為之間的關(guān)系進(jìn)行抽象。相關(guān)定義如下:

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

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

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

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

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

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

定義6 服務(wù)曲線:給定一個(gè)廣義增函數(shù)β∈F，對于一個(gè)系統(tǒng)S和流經(jīng)S的流，在輸入端和輸出端該流的累積函數(shù)分別為R和R*，當(dāng)且僅當(dāng)

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

在已知數(shù)據(jù)流到達(dá)曲線α和服務(wù)曲線β的情況下，可以得出如下幾個(gè)定理:

定理1 積壓上界:假設(shè)到達(dá)曲線為α的數(shù)據(jù)流通過一個(gè)所提供服務(wù)曲線為β的系統(tǒng)S，那么，對任意時(shí)間t，系統(tǒng)S中積壓的數(shù)據(jù)滿足

定理2 延遲上界:假設(shè)到達(dá)曲線為α的數(shù)據(jù)流通過一個(gè)所提供服務(wù)曲線為β的系統(tǒng)S，那么，對任意時(shí)間t，數(shù)據(jù)流在S中的延遲滿足

定理3 輸出上界:假設(shè)到達(dá)曲線為α的數(shù)據(jù)流通過一個(gè)所提供服務(wù)曲線為β的系統(tǒng)S，那么，輸出上界為

定理4 假設(shè)系統(tǒng)S1和S2提供的服務(wù)曲線分別為β1和β2，系統(tǒng)S1和系統(tǒng)S2串聯(lián)后提供的總服務(wù)曲線為β，則 β =β1?β2。

2 流量模型與屬性界限

2.1 感知數(shù)據(jù)到達(dá)曲線與服務(wù)曲線

假設(shè)傳感器節(jié)點(diǎn)均為同構(gòu)，監(jiān)測區(qū)域具有比較平均的數(shù)據(jù)突發(fā)率，每個(gè)節(jié)點(diǎn)均能感知并接收到監(jiān)測數(shù)據(jù)，從平均的角度看，可以認(rèn)為不同的節(jié)點(diǎn)具有相同的監(jiān)測數(shù)據(jù)量。監(jiān)測數(shù)據(jù)輸入對應(yīng)節(jié)點(diǎn)時(shí)的到達(dá)曲線滿足漏桶管制(leaky bucket regulated)［8］，到達(dá)曲線表示為

式中 rs和bs分別為每個(gè)節(jié)點(diǎn)感知范圍內(nèi)監(jiān)測數(shù)據(jù)的平均速率和突發(fā)數(shù)據(jù)大小，bs又稱為漏桶容量。

因節(jié)點(diǎn)是同構(gòu)的，故假定每個(gè)節(jié)點(diǎn)均具有相同的服務(wù)能力，其基于速率—延遲的服務(wù)曲線為

式中 Rs為節(jié)點(diǎn)服務(wù)速率，且Rs≥ri;Ts為數(shù)據(jù)在節(jié)點(diǎn)緩沖區(qū)中的最大調(diào)度延遲;(x)+=max(0，x)。

2.2 輸出上界

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

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

2.3 屬性界限

在WSNs中，傳感器節(jié)點(diǎn)的通信半徑有限，傳輸范圍不能覆蓋整個(gè)網(wǎng)絡(luò)，數(shù)據(jù)通常需要通過多跳路由轉(zhuǎn)發(fā)才能抵達(dá)基站。因此，網(wǎng)絡(luò)中數(shù)據(jù)流呈現(xiàn)不均勻狀態(tài)，數(shù)據(jù)流往基站方向匯聚，節(jié)點(diǎn)越靠近基站，則需要服務(wù)的數(shù)據(jù)流越多。對于網(wǎng)絡(luò)中的某一傳輸路徑，可以將其作為一個(gè)只接收數(shù)據(jù)流匯聚的系統(tǒng)，系統(tǒng)內(nèi)任意一跳節(jié)點(diǎn)的輸出數(shù)據(jù)全部往下一跳父節(jié)點(diǎn)傳送。這個(gè)假定符合WSNs中數(shù)據(jù)流往基站匯聚的規(guī)律。

對于節(jié)點(diǎn)i，輸入數(shù)據(jù)流為匯聚流，該匯聚流包括節(jié)點(diǎn)i自身感應(yīng)數(shù)據(jù)流和子節(jié)點(diǎn)轉(zhuǎn)發(fā)過來的數(shù)據(jù)流，如圖1所示，其到達(dá)曲線如下式所示

式中 Ni，child_all是以節(jié)點(diǎn)i為必經(jīng)路由的所有節(jié)點(diǎn)數(shù)量，即流經(jīng)節(jié)點(diǎn)i的所有轉(zhuǎn)發(fā)感應(yīng)數(shù)據(jù)流的數(shù)量。

圖1 流經(jīng)節(jié)點(diǎn)i的匯聚數(shù)據(jù)流Fig 1 Aggregate data flows traversing node i

對于某總跳數(shù)為H的傳輸路徑，源節(jié)點(diǎn)到基站的端到端延遲上界為各跳最大延遲之和，如下式

對于同構(gòu)WSNs，端到端延遲上界應(yīng)為

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

由式(5)和式(12)得到節(jié)點(diǎn)i緩沖區(qū)容量下界(即積壓上界)為

若式(16)不能滿足，則網(wǎng)絡(luò)通信繁忙時(shí)節(jié)點(diǎn)緩沖區(qū)可能溢出，造成丟包。由式(16)可知，匯聚至節(jié)點(diǎn)i的數(shù)據(jù)流越多，積壓上界越大。

為保證數(shù)據(jù)傳輸通暢，要求節(jié)點(diǎn)服務(wù)速率下界滿足

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

3 實(shí)驗(yàn)分析

以圖2所示W(wǎng)SNs拓?fù)浣Y(jié)構(gòu)［7］為例進(jìn)行數(shù)值分析。監(jiān)測區(qū)域?yàn)? d×8 d的正方形，均勻布置80個(gè)傳感器，每個(gè)傳感器節(jié)點(diǎn)通信半徑為理想的?；疚挥诜叫螀^(qū)域正中。在第一個(gè)節(jié)點(diǎn)死亡之前，節(jié)點(diǎn)總是以最短路徑進(jìn)行數(shù)據(jù)傳輸。部分傳輸路徑如圖2所示。假定為同構(gòu)WSNs，rs=0.1 kbps，bs=0.2 kb，Rs=1 Mbps，Ts=0.1 s，服務(wù)速率和節(jié)點(diǎn)緩沖區(qū)足夠大。WSNs屬性界限如表1和表2所示。

圖2 WSNs拓?fù)涫疽鈭DFig 2 Diagram of WSNs topology

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

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

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

4 結(jié)論

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

［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，F(xiàn)isal 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］梁慶偉，姚道遠(yuǎn)，鞏思亮.一種保障時(shí)延能量高效的無線傳感器網(wǎng)絡(luò)路由協(xié)議［J］.西安交通大學(xué)學(xué)報(bào)，2012，46(6):48－52.

［6］李慶華，陳志剛，黃國盛，等，基于網(wǎng)絡(luò)演算的無線自組網(wǎng)端到端延遲上界研究［J］.系統(tǒng)仿真學(xué)報(bào)，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］高文宇，陳喬松，王建新.網(wǎng)絡(luò)微積分學(xué)研究［J］.微電子學(xué)與計(jì)算機(jī)，2004，21(11):76－80.