基于CSMA/CA改進(jìn)算法的無線傳感器網(wǎng)絡(luò)OTA優(yōu)化*

謝志明, 徐 楊

(貴州大學(xué) 大數(shù)據(jù)與信息工程學(xué)院,貴州 貴陽 550000)

0 引 言

文獻(xiàn)[1]根據(jù)ZigBee聯(lián)盟的相關(guān)空中下載(over the air,OTA)標(biāo)準(zhǔn)進(jìn)行了相關(guān)的開發(fā),但對更新效率方面關(guān)注度比較少,而且必須要配合相應(yīng)的軟件才能實(shí)現(xiàn)升級。文獻(xiàn)[2]涉及無線傳感器網(wǎng)絡(luò)(wireless sensor networks,WSNs)空中下載協(xié)議,該協(xié)議為WSNs提供節(jié)點(diǎn)狀態(tài)控制、程序代碼更新等服務(wù),在實(shí)際應(yīng)用中需要進(jìn)行具體優(yōu)化。文獻(xiàn)[3]提出了點(diǎn)對點(diǎn)的無線下載方案,但數(shù)據(jù)校驗(yàn)仍不足,可能會導(dǎo)致數(shù)據(jù)錯(cuò)誤。文獻(xiàn)[4,5]在研究OTA實(shí)現(xiàn)過程的基礎(chǔ)上,設(shè)計(jì)出了一種能夠提高更新效率的鏡像頁請求方法,但要求在理想環(huán)境下進(jìn)行,沒有考慮外界因素對結(jié)果的影響。

本文針對小規(guī)模ZigBee網(wǎng)絡(luò)的多節(jié)點(diǎn)鏡像程序的同步更新升級,采用通用架構(gòu)、多點(diǎn)并發(fā)、高效的無線下載解決方案。節(jié)點(diǎn)自主向網(wǎng)絡(luò)覆蓋范圍內(nèi)的服務(wù)器或者子服務(wù)器申請鏡像程序,協(xié)調(diào)器控制OTA升級過程,從而實(shí)現(xiàn)多節(jié)點(diǎn)并發(fā)升級。該方案不僅可以解決鏡像數(shù)據(jù)在網(wǎng)絡(luò)路徑上重復(fù)傳輸?shù)膯栴},且可以解決ZigBee網(wǎng)絡(luò)中的數(shù)據(jù)冗余問題,實(shí)現(xiàn)多節(jié)點(diǎn)更新升級效率的提高。

1 OTA原理

在OTA技術(shù)[6]中,起到作用的是3個(gè)概念上的組件：協(xié)調(diào)器、服務(wù)器和客戶端。協(xié)調(diào)器組建網(wǎng)絡(luò),通過單播或廣播發(fā)送鏡像升級通知,以及激活驗(yàn)證后的新鏡像。OTA服務(wù)器通過串行總線連接到PC并下載鏡像升級程序。服務(wù)器提供了鏡像升級文件的來源,其主要負(fù)責(zé)的OTA客戶端鏡像程序升級。服務(wù)器承擔(dān)協(xié)調(diào)器和OTA客戶端之間的通信任務(wù),其負(fù)責(zé)處理由協(xié)調(diào)器和OTA客戶端發(fā)送的請求,并將鏡像文件發(fā)送給由ZigBee網(wǎng)絡(luò)提供的所有OTA客戶端。OTA客戶端通過ZigBee網(wǎng)絡(luò)連接到OTA服務(wù)器,主要負(fù)責(zé)接收和處理OTA 服務(wù)器發(fā)送的命令和鏡像文件數(shù)據(jù)。

鏡像文件傳輸過程為：當(dāng)許多OTA客戶端同時(shí)開始升級鏡像時(shí),協(xié)調(diào)器將發(fā)送鏡像升級命令到OTA服務(wù)器。OTA服務(wù)器收到升級命令后,會通過ZigBee網(wǎng)絡(luò)向所有OTA客戶端發(fā)送鏡像廣播升級通知。OTA客戶端收到升級通知后,會判斷鏡像版本是否最新。如果OTA客戶端需要升級鏡像,則鏡像程序?qū)⒂蒢igBee網(wǎng)絡(luò)從OTA服務(wù)器下載。所有OTA客戶端的鏡像數(shù)據(jù)都由OTA服務(wù)器在網(wǎng)絡(luò)中發(fā)送。在客戶端校驗(yàn)鏡像文件無誤后,還需要協(xié)調(diào)器端發(fā)送命令激活鏡像。

2 改進(jìn)的遠(yuǎn)程更新

2.1 多節(jié)點(diǎn)并發(fā)升級

本文結(jié)合現(xiàn)有的OTA技術(shù)體系結(jié)構(gòu)和P2P技術(shù)思想,提出了一種多節(jié)點(diǎn)并發(fā)升級方案[7],以提高廣播升級的效率。OTA服務(wù)器在圖1中被重命名為主服務(wù)器(master server),且所有具有服務(wù)器功能的路由器都被重命名為子服務(wù)器(subserver)。

圖1 多節(jié)點(diǎn)并發(fā)升級體系結(jié)構(gòu)

當(dāng)OTA客戶端開始廣播升級時(shí),升級過程基本類似前述升級過程。所不同的是,所有的OTA客戶端都直接將鏡像程序數(shù)據(jù)請求發(fā)送給父節(jié)點(diǎn)(主服務(wù)器或子服務(wù)器),并非所有的OTA客戶端都將請求發(fā)送到OTA服務(wù)器。主服務(wù)器從協(xié)調(diào)器接收鏡像數(shù)據(jù)并將鏡像數(shù)據(jù)發(fā)送回鏡像請求的子服務(wù)器和少部分OTA客戶端。當(dāng)子服務(wù)器完成鏡像數(shù)據(jù)的接收時(shí),其將收到的鏡像數(shù)據(jù)發(fā)送給另一部分OTA客戶端。在多節(jié)點(diǎn)并發(fā)升級方案中,所有OTA客戶端完成1個(gè)鏡像數(shù)據(jù)傳輸,且每個(gè)父節(jié)點(diǎn)(協(xié)調(diào)者除外)將僅接收鏡像程序數(shù)據(jù)。由于子服務(wù)器的功能與主服務(wù)器類似,所以子服務(wù)器可以重用主服務(wù)器的OTA服務(wù)代碼。該方案解決了鏡像數(shù)據(jù)在網(wǎng)絡(luò)路徑上重復(fù)傳輸?shù)膯栴},即數(shù)據(jù)冗余問題。與原始方法相比,本文提出的方案大大減少OTA客戶端向OTA主服務(wù)器發(fā)送鏡像請求的數(shù)量,從而減少OTA主服務(wù)器的工作量。

2.2 時(shí)延優(yōu)化方案

延時(shí)就是設(shè)備到設(shè)備之間完成數(shù)據(jù)傳送所用的時(shí)間。在CSMA/CA算法中,后退次數(shù)(number of back,NB)：當(dāng)設(shè)備有數(shù)據(jù)要傳送時(shí),發(fā)送CCA檢測,若檢測到信道忙,則會再一次產(chǎn)生倒退時(shí)間,此時(shí)NB值會加1。后退指數(shù)(backoff exponent,BE)：決定節(jié)點(diǎn)進(jìn)行CCA之前隨機(jī)退避窗口的取值。取值范圍由min(min BE,max BE)決定,考慮到BE最小值可以自由變動,如果減小BE值將會縮短退避范圍；反之，等待時(shí)間可能會增加。本文的改進(jìn)思路是對min BE和max BE值進(jìn)行自適應(yīng)調(diào)整[8],提出一種結(jié)合網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)據(jù)傳輸情況的改進(jìn)型MAC層BE修改方案。

3 非時(shí)隙CSMA/CA算法改進(jìn)

3.1 算法改進(jìn)

為了實(shí)現(xiàn)對min BE和max BE進(jìn)行自適應(yīng)調(diào)整,在改進(jìn)算法中設(shè)max_backoff為最大的退避指數(shù)[9]。為了實(shí)現(xiàn)根據(jù)沖突次數(shù)而動態(tài)改變退避上限自適應(yīng)變化值,添加一個(gè)變量abackoff。

1)若上一次嘗試傳輸?shù)拇螖?shù)大于當(dāng)前的abackoff,則將退避上限值增加到min{max_backoff,abackoff×2}。

2)若上一次嘗試傳輸?shù)拇螖?shù)小于當(dāng)前的abackoff,則將退避上限值減少到min{max_backoff/2,abackoff-1}。

這種退避上限值的方法,可以減少在輕負(fù)載或者小的網(wǎng)絡(luò)中的退避時(shí)間。

3.2 基于馬爾可夫鏈的CSMA/CA改進(jìn)算法分析

假設(shè)有n臺設(shè)備競爭信道,每臺設(shè)備1次只有1個(gè)數(shù)據(jù)包,數(shù)據(jù)包發(fā)送后,若MAC子層沒有收到正確應(yīng)答則重新發(fā)送數(shù)據(jù),直到收到正確應(yīng)答。

根據(jù)非時(shí)隙CSMA/CA機(jī)制流程,其馬爾可夫過程的狀態(tài)轉(zhuǎn)移如圖2所示。圖中每個(gè)圈代表1個(gè)狀態(tài),Tx代表發(fā)送狀態(tài),其他常量變量定義如下：idle為發(fā)送后設(shè)備處于空閑的狀態(tài)；(i,j)為節(jié)點(diǎn)進(jìn)入退避算法后的退避計(jì)數(shù)狀態(tài)；s(t)和b(t)分別為i,j的狀態(tài)。Pidle為數(shù)據(jù)包到達(dá)MAC層的概率；PTx為數(shù)據(jù)包發(fā)送等待的概率；α為執(zhí)行第一次CCA時(shí)信道為忙的概率；β為執(zhí)行第一次CCA時(shí)信道空閑的前提下,第二次執(zhí)行CCA時(shí)信道忙的概率；Wi為第i次退避時(shí)的窗口；s(t)為退避次數(shù)計(jì)數(shù)值,其取值范圍為[-1,Wi-1],當(dāng)s(t)=-1時(shí),代表第一次執(zhí)行CCA時(shí)信道為空的概率；b(t)為隨機(jī)退避時(shí),退避周期計(jì)數(shù)值。πi,j為處于(i,j) 狀態(tài)的穩(wěn)態(tài)概率,定義為πi,j=limP(s(t)=i,b(t)=j)。

根據(jù)IEEE 802.15.4的定義當(dāng)j≤N時(shí),Wj=2jW0,當(dāng)j>N時(shí),Wj=WN(W0=2BE),那么當(dāng)有2個(gè)CCA檢時(shí)計(jì)數(shù)器就減少到0。則在t時(shí)刻可以定義函數(shù)π(t)

(1)

則π(t)是圖3所構(gòu)建的具有單步轉(zhuǎn)移概率分布的離散馬爾可夫鏈。

圖2 非時(shí)隙CSMA/CA馬爾可夫鏈

根據(jù)以上條件可將概率α,β和數(shù)據(jù)傳送成功的概率Ps用πi,j,πTx,πidle表示。因?yàn)橐粋€(gè)在執(zhí)行CCA1的空閑概率1-α等于其他n-1個(gè)處于除Tx狀態(tài)之外的狀態(tài)時(shí)的概率。所以α可以表示為

α=1-(1-πTx)n-1

(2)

β為一個(gè)條件概率,其要求在CCA1時(shí)信道是空閑的條件下CCA2信道是忙狀態(tài),即

(3)

數(shù)據(jù)傳送成功的概率PS為2次CCA信道均空閑條件下數(shù)據(jù)發(fā)送成功,可用式(4)計(jì)算

(4)

根據(jù)上面定義和馬爾可夫鏈規(guī)則,在該馬爾可夫鏈模型中πi,j,πTx,πidle公式可以表示如下

若1≤i≤M,則

πi,0=(α+β-αβ)iπ0,0

(5)

若0≤i≤M,則

πi,-1=(1-α)πi,0

(6)

若0≤i≤M,則

π0,i=π0,0-((1-PTs)(1-Ps))πi,0Tx+

(1-Pidleπidle)

(7)

若1≤i≤M,1≤j≤Wi-1,則

(8)

(9)

(10)

在這個(gè)馬爾可夫鏈模型中所有穩(wěn)態(tài)概率都能由π0,0表示。由以上公式,可以計(jì)算出一個(gè)數(shù)據(jù)包發(fā)送的平均延時(shí)。

4 算法仿真驗(yàn)證與結(jié)果分析

仿真實(shí)驗(yàn)所采取的模式是遵循IEEE 802.15.4 MAC層所定義的非時(shí)隙CSMA/CA算法為基礎(chǔ)設(shè)計(jì)的。網(wǎng)絡(luò)模型參數(shù)設(shè)置如表1。

表1 網(wǎng)絡(luò)模型參數(shù)

設(shè)每個(gè)鏡像數(shù)據(jù)分組的長度為b,由OTA服務(wù)器送入OTA客戶端的總鏡像數(shù)據(jù)到達(dá)率為T個(gè)/s分組,其中成功接收率為t個(gè)/s分組,則總數(shù)據(jù)量為g=b×T(bit/s),而網(wǎng)絡(luò)的平均吞吐量為s=b×t(bit/s),若網(wǎng)絡(luò)容量(最大傳輸速率)為R(bit/s),則可定義歸一化總數(shù)據(jù)量為G=g/R,歸一化吞吐量為S=s/R。由以上定義可看出歸一化吞吐量其實(shí)就是信道容量利用率。仿真結(jié)果如圖3所示。

圖3 仿真結(jié)果

由圖3(a)可見,隨著G增大,兩者的信道利用率也逐漸增大,直至某一點(diǎn)后由于碰撞大量增加而開始下降。在信道流量G=1.5左右時(shí),吞吐量最大值由0.3增加到0.58。可見,在提高網(wǎng)絡(luò)吞吐量,提高網(wǎng)絡(luò)的更新效率上,采取了改進(jìn)算法CSMA_Pro更有優(yōu)勢。

從圖3(b)中可以看出,算法改進(jìn)后的時(shí)延比改進(jìn)前要好的多,由原來的0.029 s減少到現(xiàn)在的0.024 s,最后隨著時(shí)間的增加趨于一致,并且基本上消除了時(shí)延抖動。在IEEE 802.15.4的MAC層中規(guī)定所有節(jié)點(diǎn)的初始指數(shù)BE的默認(rèn)值在不同網(wǎng)絡(luò)中不一定是最佳值,而BE變化范圍由minBE和maxBE值決定,當(dāng)該算法的其它參數(shù)不變的情況下,這兩個(gè)值決定退避時(shí)隙的范圍大小。而改進(jìn)算法CSMA_Pro實(shí)現(xiàn)了根據(jù)沖突次數(shù)而動態(tài)改變退避值上限,從而增大退避時(shí)隙(0～2BE-1)的范圍,減小數(shù)據(jù)碰撞的概率,減小網(wǎng)絡(luò)時(shí)延,對網(wǎng)絡(luò)更新效率有明顯提升。

從圖4(c)中可以看出算法改進(jìn)后,網(wǎng)絡(luò)負(fù)載隨著時(shí)間的增加有了明顯增長,當(dāng)節(jié)點(diǎn)的網(wǎng)絡(luò)負(fù)載較小時(shí),競爭信道的節(jié)點(diǎn)比較少,數(shù)據(jù)不易產(chǎn)生沖突,網(wǎng)絡(luò)傳輸速率增大。隨著仿真時(shí)間的增加,發(fā)送數(shù)據(jù)的節(jié)點(diǎn)增多,網(wǎng)絡(luò)負(fù)載變大,到了15 s時(shí)趨于平穩(wěn),增加了1 000 bps。

5 結(jié) 論

經(jīng)過仿真實(shí)驗(yàn),確認(rèn)本文方法使得網(wǎng)絡(luò)吞吐量增加,加快網(wǎng)絡(luò)中鏡像程序的傳輸,同時(shí)相比原始網(wǎng)絡(luò)而言減少時(shí)延,從而改善無線傳感網(wǎng)絡(luò)空中下載節(jié)點(diǎn)更新效率低的問題。通過對無線傳感器中節(jié)點(diǎn)鏡像程序更新的分析仿真和驗(yàn)證,為進(jìn)一步改進(jìn)節(jié)點(diǎn)鏡像更新性能提供了思路和方法,有利于更好地應(yīng)用無線傳感網(wǎng)絡(luò)。