無線傳感網(wǎng)絡(luò)的廣播時效性研究

王 梅，彭丹丹，張壯壯

南京信息工程大學 電子與信息工程學院，南京210044

由于移動無線服務(wù)爆炸式增長，實時信息的傳播在實時系統(tǒng)和網(wǎng)絡(luò)中變得越來越重要。例如在車聯(lián)網(wǎng)絡(luò)中[1]，車輛需要及時共享其狀態(tài)位置（如位置、速度、加速度），以確保行駛安全。然而，無論是傳統(tǒng)的延遲還是吞吐量，都不太合適用來度量信息的新鮮度[2]。具體來說，當延時很小時，如果傳輸不太頻繁的話，接收到的數(shù)據(jù)包并不總是新鮮的；當吞吐量較大時，如果數(shù)據(jù)經(jīng)歷較大的隊列延遲時，接收到的數(shù)據(jù)也可能不新鮮。因此，“信息年齡”（age of information，AoI）這一概念在2011年被Kaul等人提出作為衡量信息廣播系統(tǒng)的時效性的重要指標。AoI 指最新成功接收的數(shù)據(jù)包的當前時間與生成時間之間的時間差，即接收器處最新可用的數(shù)據(jù)包的年齡。AoI用來描述接收到的數(shù)據(jù)包的新鮮度，當吞吐量非常低或非常高時，AoI就會很大。因此，AoI被認為是比吞吐量和延遲更好的及時性度量。Kaul 等人基于經(jīng)典的排隊理論方法分析了M/M/1、M/D/1和D/M/1[1]在不同服務(wù)策略下（包括先到先服務(wù)（first come first served，F(xiàn)CFS）[1，3]和后生成先服務(wù)（last generated first served，LGFS）[4]）的信息年齡。

傳統(tǒng)的AoI是從接收方考慮接收信息的時效性，非常適用于點對點通信。然而，在許多無線傳感網(wǎng)絡(luò)中，節(jié)點需要在整個網(wǎng)絡(luò)中傳播它的數(shù)據(jù)包。例如，當一輛車發(fā)生事故時，該車應(yīng)盡快將此緊急信息傳播到整個車輛網(wǎng)絡(luò)，以便其他車輛能夠做出及時且適當?shù)捻憫?yīng)。當汽車接收到來自任何鄰居的新消息時，不管消息何時生成，消息是否比先前接收到的消息更新鮮，AoI 都會發(fā)生變化，因此，本文從發(fā)送機的角度來研究網(wǎng)絡(luò)的廣播信息年齡（broadcast age of information，bAoI）。bAoI被定義為當前時刻減去剛剛廣播成功的那個數(shù)據(jù)包的生成時刻，即最新成功廣播數(shù)據(jù)包的年齡。盡管bAoI與AoI的定義相似，但是bAoI能夠研究每個信息源的廣播行為和發(fā)送到每個信息源的一跳鄰居的數(shù)據(jù)包的及時性。

在無線傳感網(wǎng)絡(luò)中，介質(zhì)訪問控制（medium access control，MAC）協(xié)議決定了無線信道的使用方式，通過在傳感器節(jié)點之間建立鏈路可以保證節(jié)點公平有效地分配有效的通信資源。載波監(jiān)聽多路訪問/沖突避免（carrier sense multiple access with collision avoidance，CSMA/CA）協(xié)議是應(yīng)用得最廣泛的一種媒體訪問控制方案。目前，人們對基于CSMA/CA 協(xié)議的信息傳播有了廣泛的研究[5-8]。文獻[5]在飽和情況下建立了馬爾可夫鏈模型來分析網(wǎng)絡(luò)的吞吐量性能，然而典型的網(wǎng)絡(luò)條件是非飽和的，文獻[6-7]進一步將此模型擴展到不飽和的環(huán)境來進行研究，文獻[8]針對不同的路由協(xié)議（如flooding、pflooding）在網(wǎng)絡(luò)覆蓋方面的廣播可靠性進行了綜合分析和比較。文獻[9]討論了網(wǎng)絡(luò)節(jié)點間的公平性問題。

本文研究了一種基于時隙CSMA/CA 的節(jié)點均勻分布的無線傳感網(wǎng)絡(luò)。在每個時隙中，每個節(jié)點以一定的概率生成一個數(shù)據(jù)包，并根據(jù)時隙CSMA/CA協(xié)議將其廣播給鄰居。本文建立該網(wǎng)絡(luò)的等效傳輸模型，分析研究節(jié)點的碰撞概率和傳輸概率。在此基礎(chǔ)上計算網(wǎng)絡(luò)的平均bAoI。通過理論和仿真驗證，節(jié)點密度和到達率等因素對網(wǎng)絡(luò)的平均bAoI 有較大的影響。平均bAoI 與密度和到達率的變化曲線是凸的。也就是說，當?shù)竭_率很小或很大時，平均bAoI會增加，并在中間達到最小值。選取合適的到達率和節(jié)點密度可以使網(wǎng)絡(luò)的平均bAoI達到最小。

1 系統(tǒng)模型

考慮如圖1所示的無線傳感器網(wǎng)絡(luò)模型，該無線傳感器網(wǎng)絡(luò)由M個節(jié)點構(gòu)成，均勻分布在一個面積為A的區(qū)域內(nèi)，則此時的節(jié)點密度為ρ=M/A。無線傳感器網(wǎng)絡(luò)中的節(jié)點都有相同的通信半徑r，若任意兩個節(jié)點之間的距離d小于或等于通信半徑r，即d≤r，則稱這兩個節(jié)點互為鄰居節(jié)點。節(jié)點服從均勻泊松分布，度的分布為：

圖1 無線傳感網(wǎng)絡(luò)模型Fig.1 Wireless sensor network model

其中，泊松分布的參數(shù)為η=ρπr2。

將時間劃分為若干相同大小的時隙，每個節(jié)點都以固定的概率在每個時隙首端生成一個數(shù)據(jù)包。如果節(jié)點在這一時隙沒有接收到來自其鄰居的數(shù)據(jù)包，其自身產(chǎn)生的數(shù)據(jù)包就被放入緩存隊列中，并在稍后廣播。否則，自身產(chǎn)生數(shù)據(jù)包將被丟棄，接收到的數(shù)據(jù)包將被保存和廣播。

網(wǎng)絡(luò)中的所有節(jié)點共享同一信道，并根據(jù)時隙CS-MA/CA 協(xié)議進行傳輸。在該協(xié)議中，每個節(jié)點由一對整數(shù)(s,t)建模。其中s指的是退避次數(shù)，從0開始，每一次傳輸嘗試導致沖突時就會增加1，最多可增加到smax；t指的是退避時間（看作一個計數(shù)器），在(0,Ws-1) 間均勻選擇。其中Ws=2sWmin，Wmin為最小競爭窗口。為了避免沖突，每一個節(jié)點在發(fā)送數(shù)據(jù)前需要等待一個退避時間。當計數(shù)器減到0的時候，節(jié)點將傳送數(shù)據(jù)。如果與其他節(jié)點的傳輸發(fā)生碰撞，節(jié)點將進行另一輪的退避，相應(yīng)的退避次數(shù)也會增加。

本文研究的網(wǎng)絡(luò)是非飽和的，一些節(jié)點沒有數(shù)據(jù)包可以傳輸，因此引入(0,t)e表示一個剛發(fā)送完數(shù)據(jù)包但是緩存沒有數(shù)據(jù)包等待的節(jié)點的狀態(tài)，其中t∈[0,W0-1]。當s>0 時，表示該節(jié)點發(fā)生了沖突，此時節(jié)點的緩存中至少有一個等待傳輸?shù)陌Ｒ虼耍谶@樣的狀態(tài)下，退避次數(shù)s=0。pidle用來表示當計數(shù)開始減少時節(jié)點緩存沒有數(shù)據(jù)包等待發(fā)送的概率，1-pidle用來表示在非飽和狀態(tài)下計數(shù)器開始減少時節(jié)點緩存至少一個包等待發(fā)送的概率。

與傳統(tǒng)的AoI 從接收者的角度度量數(shù)據(jù)包的新鮮度不同，本文提出了一種新的度量方法，即廣播信息年齡（bAoI）。

定義1廣播信息年齡等于當前時間m和最新成功廣播的數(shù)據(jù)包的生成時間U(m)之間的差值：

本文主要研究網(wǎng)絡(luò)的平均單跳的bAoI，可以表示為：

圖2 展示了bAoI 和AoI 變化的示例路徑。從圖中可以看出，bAoI在時間上呈線性增長，并重置為一個較小的值（最新成功廣播的數(shù)據(jù)包的年齡）。在這種情況下，虛線曲線所示的AoI的物理意義并不十分清楚。如果一個節(jié)點接收到一個新的數(shù)據(jù)包，而這個數(shù)據(jù)包比之前從其他鄰居收到的數(shù)據(jù)包要新鮮，那么該節(jié)點的AoI將被重置為更大的值。

圖2 bAoI和AoI的樣本路徑Fig.2 Sample paths of bAoI and AoI

2 等效模型

基于連續(xù)離散模型計算節(jié)點的新到達率，從而得到數(shù)據(jù)包的到達時間間隔分布；建立等效傳輸模型計算數(shù)據(jù)包的服務(wù)速率從而得到服務(wù)時間分布。

2.1 連續(xù)離散模型

假設(shè)每個節(jié)點在時隙首端以概率p0生成一個數(shù)據(jù)包。那么數(shù)據(jù)包k和數(shù)據(jù)包k+1 到達的時間間隔（即到達時間間隔Xk=mk+1-mk）是參數(shù)為p0的幾何分布，到達過程是Bernoulli 過程。經(jīng)過多次廣播后，每個節(jié)點的緩存中不僅包括由它自身生成的數(shù)據(jù)包，還有接收到的由該節(jié)點的鄰居轉(zhuǎn)發(fā)的數(shù)據(jù)包，則此時新到達率p大于初始到達率p0。然而，在離散時間狀態(tài)下，新到達率的計算比較困難。因此，考慮在連續(xù)時間狀態(tài)下進行研究。

通過在指數(shù)和幾何分布之間建立一個連續(xù)-離散模型來計算在離散狀態(tài)下的新到達率。如表1所示，伯努利過程是泊松過程的離散化，即指數(shù)分布是幾何分布的連續(xù)模擬。

表1 泊松過程與伯努利過程Table 1 Poisson process versus Bernoulli process

在已知離散狀態(tài)下的到達率p0的情況下，連續(xù)時間狀態(tài)下的初始到達率λ0可以表示為：

在連續(xù)時間狀態(tài)下，可以將節(jié)點自身生成的數(shù)據(jù)包與接收相鄰節(jié)點轉(zhuǎn)發(fā)的數(shù)據(jù)包的過程看作一個新的泊松過程，該過程具有新的參數(shù)λ。因此，節(jié)點的新到達率λ與三個參數(shù)有關(guān)，即自身到達率λ0、鄰居到達率和轉(zhuǎn)發(fā)概率pfw。

考慮到節(jié)點不接收自身已經(jīng)廣播的數(shù)據(jù)包，新的到達率λ可以得到：

通過簡化計算，可以得到新的到達率λ的表達式：

那么，在離散狀態(tài)下節(jié)點的新到達率p可以表示為：

2.2 傳輸模型

根據(jù)文獻[10]，利用發(fā)送概率ptx和碰撞概率pcl建立了一個等效的傳輸模型。具體來說，發(fā)送概率就是每個節(jié)點在每個時隙發(fā)送數(shù)據(jù)包的概率；碰撞概率指的是節(jié)點在傳輸時發(fā)生碰撞的概率。這兩個概率不管重傳次數(shù)還是退避狀態(tài)，都是相同獨立的常數(shù)。

根據(jù)文獻[6-7]可以得到發(fā)送概率和碰撞概率的計算公式。再結(jié)合文獻[11-12]中的化簡方法，這兩個公式可以表示為：

由于每個以r為半徑的區(qū)域的節(jié)點數(shù)N是泊松分布，每個節(jié)點的平均碰撞概率可以寫成：

假設(shè)在每個時隙中，每個具有非空緩沖區(qū)的節(jié)點嘗試以概率ptx來廣播其數(shù)據(jù)包，會以概率發(fā)生碰撞。結(jié)合方程（8）和（9）可以求解ptx和。

當一個節(jié)點向其鄰居發(fā)送數(shù)據(jù)包時，只有當該節(jié)點獲得信道并且沒有發(fā)生沖突時，發(fā)送才會成功。因此，成功廣播的概率（也是數(shù)據(jù)包的服務(wù)率）可以表示為：

將節(jié)點獲取信道并成功地傳遞數(shù)據(jù)包k的時間表示為Sk。那么，Sk是參數(shù)為μ的幾何分布，概率分布可以寫成：

3 網(wǎng)絡(luò)的bAoI

首先根據(jù)已知的到達間隔時間和服務(wù)時間的統(tǒng)計特性建立排隊模型，然后計算第P(P>1) 跳的平均bAoI。基于以上結(jié)果，進一步計算每個節(jié)點廣播自己生成的數(shù)據(jù)包時的平均bAoI。

3.1 排隊模型

由于經(jīng)過多次廣播，節(jié)點的緩存中不僅包含來自自身的數(shù)據(jù)包，還包含接收的來自相鄰節(jié)點的數(shù)據(jù)包。因此，在每個時隙首端，數(shù)據(jù)包以概率p到達。數(shù)據(jù)包的到達時間Xk是呈幾何分布的，可以得到Ε[X]=1/p，。服務(wù)時間Sk也服從幾何分布，有Ε[S]=1/μ。

由此可知節(jié)點的廣播過程為Geom/Geom/1 排隊模型，即到達過程為Bernoulli 過程，服務(wù)過程是幾何過程。根據(jù)文獻[13]，一般Geom/Geom/1 隊列中，節(jié)點緩存為空的概率可以表示成：

由于式（8）和（9）是非線性的，需要一個數(shù)值算法來進行計算。基于式（13）給出的空閑概率，本文提出了一種迭代算法來計算ptx和，具體如下所示。

根據(jù)文獻[14]，系統(tǒng)時間Tk是數(shù)據(jù)包k的等待時間與服務(wù)時間之和，服從參數(shù)為1-υ的幾何分布：

3.2 第P(P>1) 跳的廣播信息年齡

離開時間間隔Yk表示兩次連續(xù)成功廣播的數(shù)據(jù)包之間的時間。根據(jù)文獻[14]可知，對于Geom/Geom/1排隊模型，離開時間間隔服從參數(shù)為p的幾何分布。

數(shù)據(jù)包k-1 的系統(tǒng)時間Tk-1可以表示為：

由于服務(wù)時間Sk與到達間隔時間Xk相互獨立，可以得到：

因為Wk=max(0,Tk-1-Xk)，所以Xk與Wk相關(guān)。根據(jù)文獻[3]，構(gòu)建一個輔助函數(shù)H(z)來計算Ε[XkWk]，如下所示：

利用輔助函數(shù)H(z)，可以得到：

根據(jù)式（16）和式（18），第P(P>1) 跳的平均bAoI可表示為：

3.3 第一跳的廣播信息年齡

在每個時隙中，每個節(jié)點都以概率p0生成自己的數(shù)據(jù)包，到達時間間隔是呈幾何分布的，因此可以得到。離開時間間隔服從參數(shù)為p0的幾何分布。

與Xk之間的比值R可由p0與p之間的關(guān)系求得，因此比率的期望值可表示為：

其中Ε[XkWk]由式（18）給出。

第一跳的平均bAoI可以表示為：

因此，在已知跳數(shù)h的情況下，網(wǎng)絡(luò)的平均bAoI可以表示為：

4 仿真結(jié)果

為了驗證提出方法的有效性，用蒙特卡羅模擬來驗證計算結(jié)果。最小競爭窗口Wmin=16，最大退避次數(shù)smax=3，通信半徑r=6 m，初始到達概率p0=0.01，轉(zhuǎn)發(fā)概率pfw=0.1，跳數(shù)h=2。

4.1 節(jié)點密度的影響

圖3（a）和圖3（b）分別展示發(fā)送概率和碰撞概率隨節(jié)點密度的變化情況。從圖中可以發(fā)現(xiàn)，發(fā)送概率ptx和碰撞pcl是密度的函數(shù)。首先，可以看到發(fā)送概率ptx隨著密度ρ的增加而減少，而碰撞概率pcl隨著密度的增加而增加。這是因為當節(jié)點密度變大時，每個節(jié)點將有更多的鄰居節(jié)點和更多的傳輸爭用。這樣，碰撞概率就會增加，而傳輸碰撞的增加，則會導致傳輸概率變小。

圖3 發(fā)送概率和碰撞概率隨節(jié)點密度的變化情況Fig.3 Change of transmission probability and collision probability with node density

圖4 反映了平均bAoI 隨節(jié)點密度ρ的變化情況。從圖中可以發(fā)現(xiàn)平均bAoI的理論結(jié)果與蒙特卡羅結(jié)果基本符合。結(jié)果表明，平均bAoI 是關(guān)于ρ的凸函數(shù)。平均bAoI 隨ρ先減小，后隨ρ增大而增大。當ρ較小時，平均bAoI 較大。當ρ變大時，新到達率p也變大。在確保的情況下，當ρ接近最大密度時，平均bAoI 將趨于無窮大。這是因為當節(jié)點密度增加時，數(shù)據(jù)包生成得非常頻繁，導致碰撞也發(fā)生得更頻繁。

圖4 節(jié)點密度ρ 對平均bAoI的影響Fig.4 Average bAoI versus node density ρ

4.2 初始到達率的影響

初始到達率對平均bAoI的影響由圖5所示，其中節(jié)點密度ρ=0.04。從圖中可以發(fā)現(xiàn)平均bAoI 也是關(guān)于p0的凸函數(shù)。平均bAoI先隨著p0的增大而減小，后隨著p0增大而增大。由于新到達率p隨初始到達率p0的增大而增大，在接下來的跳數(shù)中，每個節(jié)點將在每時隙首端以概率為p生成數(shù)據(jù)包。具體地說，當p很小時，平均bAoI較大。這是因為隊列中的數(shù)據(jù)包較少，導致系統(tǒng)的等待時間更長。當p變大時，數(shù)據(jù)包生成得十分頻繁，相應(yīng)的平均bAoI也很大。

圖5 初始到達率p0 對平均bAoI的影響Fig.5 Average bAoI versus arrival rate p0

從圖4 和圖5 可以看出，節(jié)點密度ρ和初始到達率p0的變化都會引起新到達率p的變化，為了減少網(wǎng)絡(luò)的平均bAoI，節(jié)點密度或初始到達率既不能太大也不能太小。

5 結(jié)束語

本文提出了一種基于時隙CSMA/CA 協(xié)議的無線傳感網(wǎng)絡(luò)中度量信息時效性的方法。提出的廣播信息年齡從發(fā)射機的角度量化了信息的新鮮程度。首先，根據(jù)時隙CSMA/CA 協(xié)議，推導節(jié)點廣播成功的概率，結(jié)合對節(jié)點的到達過程的分析，推導出平均廣播信息年齡的閉式表達式。仿真結(jié)果表明，節(jié)點的密度和初始到達率對平均bAoI有較大的影響。可以合理地控制節(jié)點的信息產(chǎn)生過程和信息轉(zhuǎn)發(fā)過程，降低信息的碰撞概率，提高信息傳輸?shù)某晒Ω怕剩岣咝畔V播的時效性。

本文考慮的是每個數(shù)據(jù)包可以在一個時隙中傳輸完成的情況。對于數(shù)據(jù)包需要更多傳輸時隙的情況，基于服務(wù)器休假排隊的平均bAoI 可以得到，并將在以后的工作中進行研究。