王 梅，彭丹丹，張壯壯

南京信息工程大學(xué) 電子與信息工程學(xué)院，南京210044

由于移動(dòng)無線服務(wù)爆炸式增長，實(shí)時(shí)信息的傳播在實(shí)時(shí)系統(tǒng)和網(wǎng)絡(luò)中變得越來越重要。例如在車聯(lián)網(wǎng)絡(luò)中[1]，車輛需要及時(shí)共享其狀態(tài)位置（如位置、速度、加速度），以確保行駛安全。然而，無論是傳統(tǒng)的延遲還是吞吐量，都不太合適用來度量信息的新鮮度[2]。具體來說，當(dāng)延時(shí)很小時(shí)，如果傳輸不太頻繁的話，接收到的數(shù)據(jù)包并不總是新鮮的；當(dāng)吞吐量較大時(shí)，如果數(shù)據(jù)經(jīng)歷較大的隊(duì)列延遲時(shí)，接收到的數(shù)據(jù)也可能不新鮮。因此，“信息年齡”（age of information，AoI）這一概念在2011年被Kaul等人提出作為衡量信息廣播系統(tǒng)的時(shí)效性的重要指標(biāo)。AoI 指最新成功接收的數(shù)據(jù)包的當(dāng)前時(shí)間與生成時(shí)間之間的時(shí)間差，即接收器處最新可用的數(shù)據(jù)包的年齡。AoI用來描述接收到的數(shù)據(jù)包的新鮮度，當(dāng)吞吐量非常低或非常高時(shí)，AoI就會(huì)很大。因此，AoI被認(rèn)為是比吞吐量和延遲更好的及時(shí)性度量。Kaul 等人基于經(jīng)典的排隊(duì)理論方法分析了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是從接收方考慮接收信息的時(shí)效性，非常適用于點(diǎn)對(duì)點(diǎn)通信。然而，在許多無線傳感網(wǎng)絡(luò)中，節(jié)點(diǎn)需要在整個(gè)網(wǎng)絡(luò)中傳播它的數(shù)據(jù)包。例如，當(dāng)一輛車發(fā)生事故時(shí)，該車應(yīng)盡快將此緊急信息傳播到整個(gè)車輛網(wǎng)絡(luò)，以便其他車輛能夠做出及時(shí)且適當(dāng)?shù)捻憫?yīng)。當(dāng)汽車接收到來自任何鄰居的新消息時(shí)，不管消息何時(shí)生成，消息是否比先前接收到的消息更新鮮，AoI 都會(huì)發(fā)生變化，因此，本文從發(fā)送機(jī)的角度來研究網(wǎng)絡(luò)的廣播信息年齡（broadcast age of information，bAoI）。bAoI被定義為當(dāng)前時(shí)刻減去剛剛廣播成功的那個(gè)數(shù)據(jù)包的生成時(shí)刻，即最新成功廣播數(shù)據(jù)包的年齡。盡管bAoI與AoI的定義相似，但是bAoI能夠研究每個(gè)信息源的廣播行為和發(fā)送到每個(gè)信息源的一跳鄰居的數(shù)據(jù)包的及時(shí)性。

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

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

1 系統(tǒng)模型

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

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

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

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

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

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

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

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

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

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

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

2 等效模型

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

2.1 連續(xù)離散模型

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

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

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

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

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

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

通過簡化計(jì)算，可以得到新的到達(dá)率λ的表達(dá)式：

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

2.2 傳輸模型

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

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

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

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

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

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

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

首先根據(jù)已知的到達(dá)間隔時(shí)間和服務(wù)時(shí)間的統(tǒng)計(jì)特性建立排隊(duì)模型，然后計(jì)算第P(P>1) 跳的平均bAoI?；谝陨辖Y(jié)果，進(jìn)一步計(jì)算每個(gè)節(jié)點(diǎn)廣播自己生成的數(shù)據(jù)包時(shí)的平均bAoI。

3.1 排隊(duì)模型

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

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

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

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

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

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

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

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

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

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

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

3.3 第一跳的廣播信息年齡

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

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

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

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

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

4 仿真結(jié)果

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

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

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

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

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

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

4.2 初始到達(dá)率的影響

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

圖5 初始到達(dá)率p0 對(duì)平均bAoI的影響Fig.5 Average bAoI versus arrival rate p0

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

5 結(jié)束語

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

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