基于節(jié)點狀態(tài)更新的DBTMA改進方法

李付勇，夏潔，姜勝明

（上海海事大學信息工程學院，上海201306）

0 引言

MAC[1,2]（Medium Access Control）協(xié)議是無線多跳網(wǎng)絡(luò)[3]（Multi-Hop Wireless Network）的基礎(chǔ)，控制著節(jié)點對無線媒介的占用，決定了無線信道的使用方式，其性能直接影響了整個網(wǎng)絡(luò)的性能。無線自組網(wǎng)中信道共享且受節(jié)點發(fā)射功率限制，每個通信節(jié)點的傳輸范圍是受到限制的。通常需要中間節(jié)點作為中繼實現(xiàn)節(jié)點間多跳通信，因此數(shù)據(jù)沖突與節(jié)點所在位置相關(guān)。此外，無線通信中，受到障礙物和信道衰落的影響節(jié)點間通信會出現(xiàn)時延。綜上傳輸范圍、節(jié)點位置和時延等因素,無線網(wǎng)絡(luò)中隱藏終端和暴露終端[4,5]的問題是無法避免的。終端問題嚴重降低了MAC協(xié)議的性能，為了獲得更高的信道利用率、更低的延遲和更加公平的競爭，必須解決終端問題。

隱藏終端是指在接收方通信范圍內(nèi)且在發(fā)送方通信范圍之外的節(jié)點，而暴露終端指的是在發(fā)送方的通信范圍內(nèi)且在接收方傳輸范圍之外的節(jié)點。

以隱藏終端問題為例:當一個節(jié)點發(fā)送數(shù)據(jù)時，在其傳輸范圍之外的節(jié)點無法察覺到有其他節(jié)點正在發(fā)送數(shù)據(jù)，這可能會導致數(shù)據(jù)沖突。如圖1所示，當A向B發(fā)送數(shù)據(jù)時，C也向B發(fā)送數(shù)據(jù)，因此，這兩組消息將在B發(fā)生沖突，導致傳輸失敗。此時，C被稱為隱藏終端。

圖1 隱藏終端示意圖

針對以上終端問題，已有方法總結(jié)如下：1）通過發(fā)送忙音信號通知鄰居節(jié)點，如BTMA協(xié)議系列；2）數(shù)據(jù)傳輸之前，發(fā)送方首先發(fā)送請求幀給接收方，接收方收到請求時以確認幀的方式告知其他鄰居節(jié)點它即將進行接收，即 RTS/CTS[6]方式，如 CSMA/CA、MACA[7]、MACAW[8]、FAMA[9]。綜上解決方法，解決隱藏終端的關(guān)鍵是如何通知鄰居節(jié)點了解接收節(jié)點的接收狀態(tài)。本文提出一種基于節(jié)點狀態(tài)更新的DBTMA[10,11]改進方法，該方法通過實時監(jiān)控、更新并收集節(jié)點狀態(tài)來判斷是否進行數(shù)據(jù)傳輸。仿真表明該方法準確掌握接收節(jié)點的行為，減少請求握手次數(shù)和狀態(tài)誤判，從而有效避免隱藏終端問題，提高數(shù)據(jù)傳輸效率、網(wǎng)絡(luò)吞吐量和信道利用率。

1 相關(guān)工作

1.1 DBTMA 協(xié)議介紹[12]

DBTMA全稱為雙忙音多址接入?yún)f(xié)議，該協(xié)議采用多信道方式——將信道分為兩個彼此獨立的子信道：數(shù)據(jù)信道和控制信道。在數(shù)據(jù)信道上發(fā)送數(shù)據(jù)，在控制信道上發(fā)送控制幀（RTS和CTS），并且在控制信道上增加忙音信號BT（t發(fā)送忙音）——表明數(shù)據(jù)信道正在傳輸數(shù)據(jù)和忙音信號BTr（接收忙音）——表明數(shù)據(jù)信道上正在接收數(shù)據(jù)。BTt發(fā)送忙音信號為RTS幀的傳輸提供保護，并增加接收方的RTS接收成功率;BTr對RTS做出響應(yīng)并為傳輸?shù)臄?shù)據(jù)提供連續(xù)的保護。所有聽到任何忙音的節(jié)點都不允許發(fā)送RTS請求。當收聽BTr信號建立時，發(fā)送RTS幀的節(jié)點需要立即放棄傳輸。隱藏終端因為偵聽到BTr忙音信號不會發(fā)送數(shù)據(jù)，避免了數(shù)據(jù)沖突的發(fā)生因而得到解決。

1.2 DBTMA協(xié)議工作方式

工作于DBTMA協(xié)議的節(jié)點共有七種狀態(tài)，具體如表1：

表1 DBTMA的七種狀態(tài)描述

DBTMA協(xié)議的工作方式通過圖2隱藏終端示意圖進行解釋。

圖2

2 基于節(jié)點狀態(tài)更新的DBTMA改進方法

2.1 設(shè)計節(jié)點狀態(tài)碼結(jié)構(gòu)

根據(jù)1.2 DBTMA協(xié)議工作方式一節(jié)可知，運行DBTMA協(xié)議的節(jié)點必然處于以下七個狀態(tài)之一IDLE，CONTEND，S_RTS，S_DATA，WF_BTR，WF_DATA，WAIT?；诖?，設(shè)計一個7位二進制節(jié)點狀態(tài)碼：如表2：

表2 節(jié)點狀態(tài)碼結(jié)構(gòu)

以1表示在此狀態(tài)，0表示不在此狀態(tài)，從而每個節(jié)點都有一個狀態(tài)碼，此狀態(tài)碼用來描述節(jié)點狀態(tài)信息。由此可以得到七個基于二進制的7位二進制狀態(tài)碼status_code（如表 2）：0000001WAIT,0000010WF_DATA,0000100WF_BTR,0001000S_DATA,0010000S_RTS,0100000CONTEND,1000000 IDLE。

2.2 設(shè)計狀態(tài)碼表

基于節(jié)點狀態(tài)碼和DBTMA協(xié)議忙音策略設(shè)計節(jié)點狀態(tài)碼計劃表，如表3：

表3 節(jié)點狀態(tài)碼計劃表結(jié)構(gòu)

btt字段為1表示當前節(jié)點建立btt信號，btr字段為1表示當前節(jié)點建立btr信號，is_busy字段為1代表當前有忙音信號（即節(jié)點btt或btr任意字段值為1）。

2.3 狀態(tài)表信息的收集

傳統(tǒng)收集網(wǎng)絡(luò)節(jié)點信息的方法都是廣播，但是廣播代價是不容忽視的。為此，提出以下優(yōu)化方法：以集群式網(wǎng)絡(luò)為例。根據(jù)2.1設(shè)計節(jié)點狀態(tài)碼結(jié)構(gòu)可知，節(jié)點處于IDLE（空閑）狀態(tài)時狀態(tài)碼為1000000，此時節(jié)點狀態(tài)碼最大負載最小。周圍鄰居節(jié)點將各自的狀態(tài)碼發(fā)送至此節(jié)點并將其作為鄰居的負載點，如果有多個最大狀態(tài)碼的節(jié)點，隨機選擇一個作為負載點。

2.4 狀態(tài)表數(shù)據(jù)信息的共享和更新

根據(jù)2.3節(jié)點狀態(tài)信息的收集得到鄰居節(jié)點的負載點，該負載點擁有鄰居節(jié)點的所有狀態(tài)碼（包括自己的狀態(tài)碼）。負載點將鄰居節(jié)點的所有狀態(tài)碼信息封裝在狀態(tài)表中，并將表信息發(fā)送至周圍鄰居節(jié)點，從而各個節(jié)點均知道了鄰居節(jié)點的狀態(tài)碼。網(wǎng)絡(luò)中各節(jié)點均按此規(guī)則收集鄰居節(jié)點的狀態(tài)碼，從而得到網(wǎng)絡(luò)中所有節(jié)點的狀態(tài)碼。由于無線網(wǎng)絡(luò)中所有節(jié)點均有可能發(fā)生移動且節(jié)點狀態(tài)隨時變化。因此負載點的選取和狀態(tài)表信息均需要及時更新，具體更新策略為：節(jié)點狀態(tài)碼同步更新到狀態(tài)表中；上次確定為負載點的節(jié)點主動向周圍鄰居節(jié)點發(fā)出狀態(tài)碼快照并收集到狀態(tài)表中，比較個節(jié)點的狀態(tài)碼大小；將各節(jié)點狀態(tài)碼發(fā)送至周圍鄰居節(jié)點并確定狀態(tài)碼最大的節(jié)點作為負載點而本次作為負載點的節(jié)點主動放棄下次負載點的機會。

以圖3集群網(wǎng)絡(luò)示意圖為例，具體闡述節(jié)點狀態(tài)碼數(shù)據(jù)的收集和共享細節(jié)：

圖3 集群網(wǎng)絡(luò)示意圖

圖中共有A、B、C、D四個集群以及一個中心節(jié)點E。網(wǎng)絡(luò)初始化時，假設(shè)A3,B3,C3,D3分別為各自集群中狀態(tài)碼最大的節(jié)點。A集群中A（ii=1，2，4，5）分別將各自的狀態(tài)碼發(fā)送給A3節(jié)點，B集群中B（ii=1，2，4，5）分別將各自的狀態(tài)碼發(fā)送給B3節(jié)點，C集群和D集群以此類推。A3、B3、C3、D3分別拿到各自集群中所有節(jié)點的狀態(tài)碼，A3、B3、C3、D3再將各自集群中的狀態(tài)碼發(fā)送給中心節(jié)點E，至此E節(jié)點拿到網(wǎng)絡(luò)中所有節(jié)點的狀態(tài)碼。E節(jié)點將所有節(jié)點的狀態(tài)碼數(shù)據(jù)封裝在狀態(tài)表中并將此表下發(fā)給 A3、B3、C3、D3。A3、B3、C3、D3再將狀態(tài)表發(fā)給所在集群中的其他節(jié)點。至此，網(wǎng)絡(luò)中所有節(jié)點均擁有了網(wǎng)絡(luò)內(nèi)各個節(jié)點的狀態(tài)碼。

2.5 基于狀態(tài)表的決策

基于狀態(tài)表決策流程圖，如圖4所示。以圖1隱藏終端示意圖為例，其具體決策機制結(jié)合狀態(tài)表具體闡述如下：

說明：

條件1,4：查看狀態(tài)表有btt字段值為1的鄰居節(jié)點

條件2,5：查看狀態(tài)表無is_busy字段值為1的鄰居節(jié)點

條件3：查看狀態(tài)表有is_busy字段值為1的鄰居節(jié)點

網(wǎng)絡(luò)初始化時，各節(jié)點均處于IDLE狀態(tài)，此時狀態(tài)表數(shù)據(jù)如表4：

圖4 節(jié)點決策流程圖

表4

（1）當節(jié)點A100000有數(shù)據(jù)分組需要向B1000000發(fā)送，滿足條件2時更新自身狀態(tài)碼為，即（2）建立BTt信號進入S_RTS狀態(tài)，此時狀態(tài)表數(shù)據(jù)如表5：

表5

表6

B1000000接收到A節(jié)點發(fā)送的RTS請求幀，BTr字段設(shè)為1，之后建立起定時器并進入WF_DATA狀態(tài)，即B1000000更新自身狀態(tài)碼為，此時狀態(tài)表數(shù)據(jù)如表7：

表7

節(jié)點A0000100持續(xù)查看狀態(tài)表發(fā)現(xiàn)建立了BTr信號，確認自己的信道請求成功。（4）等待一段時間進入WAIT狀態(tài)，即更新自身狀態(tài)碼為A0000001，此時狀態(tài)表數(shù)據(jù)如表8：

表8

A0000001定時器超時后，（5）進入S_DATA狀態(tài)即更新自身狀態(tài)碼為A0001000，此時狀態(tài)表數(shù)據(jù)如表9：

表9

A0001000傳輸完成，（6）重新進入IDLE狀態(tài)，即更新自身狀態(tài)碼為A1000000，此時狀態(tài)表數(shù)據(jù)如表10；

表10

表11

同理，當 A100000滿足條件3時，（7）進入CONTEND狀態(tài)，即更新自身狀態(tài)碼為A0100000并同步到狀態(tài)表中；A0100000收到RTS時，（8）滿足條件4時，建立BTr進入WF_DATA狀態(tài)，即更新自身狀態(tài)碼為并同步更新到狀態(tài)表；（9）接收完數(shù)據(jù)分組或等待數(shù)據(jù)超時后進入IDLE狀態(tài)，即更新自身狀態(tài)碼為A1000000。當滿足條件5時進入S_RTS狀態(tài)，即更新自身狀態(tài)碼為并同步更新到狀態(tài)表。

同理，當 A100000滿足條件1時，（10）進入WF_DATA狀態(tài)，即更新自身狀態(tài)碼為并同步更新到狀態(tài)表；（9）接收完數(shù)據(jù)分組或等待數(shù)據(jù)超時后進入IDLE狀態(tài)，即更新自身狀態(tài)碼為A1000000。

2.6 基于狀態(tài)碼更新的隱藏終端理論研究分析

如圖1隱藏終端示意圖，A節(jié)點向B節(jié)點發(fā)送數(shù)據(jù)時，即A節(jié)點處于A0001000狀態(tài),B節(jié)點處于狀態(tài)，此時網(wǎng)絡(luò)中節(jié)點狀態(tài)表數(shù)據(jù)信息如表12。

表12

2.7 基于狀態(tài)碼更新的隱藏終端平臺研究分析

（1）nRF51822藍牙協(xié)議

本文提出的基于節(jié)點更新狀態(tài)DBTMA改進方法的實際實現(xiàn)平臺是基于nRF51822藍牙協(xié)議，該協(xié)議的分析模型如圖5：

圖5 nRF51822藍牙協(xié)議分層模型

主協(xié)議層的 GAP（Generic Access Profile）,管理廣播和連接的有關(guān)參數(shù)且具有以下特征：

①角色

GAP中規(guī)定一個設(shè)備不是集中器角色就是外圍設(shè)備角色，集中器是連接的發(fā)起者，外圍設(shè)備是被連接者，相當于鏈路層的主機和從機。另外該藍牙協(xié)議規(guī)范還定義了觀察者角色和廣播者角色，觀察者角色只監(jiān)聽空中事件，廣播者角色只廣播信息而不接收信息。

②廣播

集中器能夠與外圍設(shè)備建立連接，外圍設(shè)備必須處于廣播狀態(tài)，它每經(jīng)過一個時間間隔發(fā)送一次廣播數(shù)據(jù)包，這個時間間隔稱為廣播間隔，它的范圍是20ms到10.24s，廣播間隔影響建立連接的時間。

集中器發(fā)送一個連接請求來發(fā)起連接之前，必須接收到一個廣播數(shù)據(jù)包，外圍設(shè)備發(fā)送一個廣播數(shù)據(jù)包之后一小段時間內(nèi)只監(jiān)聽連接請求。

一個廣播數(shù)據(jù)包最多能攜帶31字節(jié)的數(shù)據(jù)，它通常包含用戶可讀的名字、關(guān)于設(shè)備發(fā)送數(shù)據(jù)包的有關(guān)信息、用于表示此設(shè)備是否可被發(fā)現(xiàn)的標志等類似的標志。

當集中器接收到廣播數(shù)據(jù)包后,它可能發(fā)送請求更多數(shù)據(jù)包的請求，稱為掃描回應(yīng)，如果它被設(shè)置成主動掃描，外圍設(shè)備將會發(fā)送一個掃描回應(yīng)做為對集中器請求的回應(yīng)，掃描回應(yīng)最多可以攜帶31字節(jié)的數(shù)據(jù)。

③掃描

掃描是集中器監(jiān)聽廣播數(shù)據(jù)包和發(fā)送掃描請求的過程，它有2個定時參數(shù)：掃描窗口和掃描間隔。

（2）nRF51822藍牙協(xié)議在基于節(jié)點更新狀態(tài)DBTMA改進方法的應(yīng)用

基于節(jié)點更新狀態(tài)DBTMA改進方法的狀態(tài)表信息存放于外圍設(shè)備的廣播數(shù)據(jù)包中，當集中器角色發(fā)起連接前，首先查看數(shù)據(jù)包中鄰居節(jié)點的狀態(tài)碼。根據(jù)2.5節(jié)基于狀態(tài)表的決策策略是否發(fā)起連接，當外圍角色監(jiān)聽到集中器的連接請求時更新自身狀態(tài)碼到廣播數(shù)據(jù)包中的狀態(tài)碼中。此時，當別的集中器接收到外圍設(shè)備的廣播數(shù)據(jù)包時，查看其狀態(tài)碼信息發(fā)現(xiàn)外圍設(shè)備正在接收數(shù)據(jù)。因而，不會發(fā)送請求到外圍設(shè)備，隱藏終端問題得以在實際平臺中實現(xiàn)。

3 基于節(jié)點更新狀態(tài)DBTMA改進方法的仿真

為了測試和分析基于節(jié)點更新狀態(tài)DBTMA改進方法的有效性和性能。本節(jié)在仿真環(huán)境下，通過改變原MAC幀結(jié)構(gòu)，即在原MAC幀中加入本文所提出的7位二進制狀態(tài)碼，觀察各個協(xié)議之間的性能。每次仿真結(jié)果為每10次運行結(jié)果的平均值。

仿真環(huán)境：首先，研究了不同隱藏終端情況下的各方案的性能。我們在具有N(N=1,2,…,6)個獨立網(wǎng)絡(luò)集群和一個公共接收節(jié)點Ad Hoc網(wǎng)絡(luò)中模擬各個協(xié)議。每個集群有5個節(jié)點，每個節(jié)點通信范圍內(nèi)互通。以N=4為例，如圖2。RTS數(shù)據(jù)幀長度為200b，數(shù)據(jù)包長度為4096b，信道傳輸速率為1M/S。圖6比較了在相同環(huán)境下各個協(xié)議方案的性能。

圖6 協(xié)議性能對比圖

從圖6中我們可以看出基于節(jié)點狀態(tài)更新的方法相比較于其他任何一種MAC方案有著更高的吞吐量。當N為1時，該方法的網(wǎng)絡(luò)利用率低于DBTMA這是由于狀態(tài)表的首先收集網(wǎng)絡(luò)中各個節(jié)點的狀態(tài)碼并通知集群中的各個節(jié)點，造成初始時效率低于DBTMA協(xié)議。但是當N≥2時，該方法相對于DBTMA信道利用率和吞吐量明顯更具有優(yōu)勢，因為本文提出的基于節(jié)點狀態(tài)更新的解決方法初始時以很小的代價收集網(wǎng)絡(luò)中各個節(jié)點狀態(tài)信息。狀態(tài)表準確實時地更新各節(jié)點的接收狀態(tài)，減少對接收端握手請求次數(shù)和避免對接收端接收計劃的誤判，從而能夠大大提高網(wǎng)絡(luò)的吞吐量和信道利用率。

4 結(jié)語

本文在深入學習MAC層隱藏終端和暴露終端問題研究的基礎(chǔ)上，提出了一種基于節(jié)點更新狀態(tài)的DBTMA改進方法，巧妙利用各個節(jié)點狀態(tài)設(shè)計節(jié)點狀態(tài)碼結(jié)構(gòu)并封裝狀態(tài)碼信息于狀態(tài)表，狀態(tài)表實時收集并更新節(jié)點狀態(tài)碼信息。節(jié)點基于狀態(tài)表信息判斷是否發(fā)送數(shù)據(jù)，該方法相比較于DBTMA協(xié)議，通過減少對接收端握手請求次數(shù)，提高了網(wǎng)絡(luò)吞吐量和信道利用率，避免了對接收端接收計劃的誤判從而數(shù)據(jù)傳輸更加準確有效。