采用時分多址的主動式高動態傳感器路由協議

朱超軍

(1. 四川大學 計算機學院， 四川 成都 610000;2. 四川司法警官職業學院 司法信息管理系， 四川 德陽 618000)

采用時分多址的主動式高動態傳感器路由協議

朱超軍1,2

(1. 四川大學 計算機學院， 四川 成都 610000;2. 四川司法警官職業學院 司法信息管理系， 四川 德陽 618000)

提出一種基于移動無線傳感器網絡(MWSN)的主動式高動態傳感器路由(AHDSR)協議.通過簡單的跳數度量，使數據朝移動環境中的匯聚節點路由時保持動態和魯棒.AHDSR協議使用時分多址(TDMA)MAC層保持移動環境中梯度指標，同時,使用盲轉發技術將信息以多途徑的方式在網絡中傳遞.運用OPNET建模模塊進行仿真，并提供一種離散時間仿真器.仿真結果表明:與其他同類方法相比，提出的協議在數據包投遞率、平均數據包時延、吞吐量和開銷方面的表現更加適合多種移動網絡場景.

移動無線傳感器網絡； 路由協議； 時分多址； 魯棒性； 動態

Abstract： Concerning the poor reliability of most existing routing protocols used in mobile wireless sensor networks (MWSN), active high dynamic sensor routing (AHDSR) based on MWSN is proposed. The proposed protocol is based on a simple hop metric, which enable the data to remain dynamic and robust when routing the sink node in the mobile environment. AHDSR maintains a gradient metric in mobile environments by using a global time division multiple access (TDMA) MAC layer. It also uses the technique of blind forwarding to pass messages through the network in a multipath manner. The effectiveness of the proposed protocol is verified by the simulation results. Compared with other similar methods, data packet delivery ratio, average packet delay throughput and overhead of the proposed protocol are more suitable for a variety of mobile network scenarios.

Keywords： mobile wireless sensor networks; routing protocols; time division multiple access; roubst; dynamic

無線傳感器網絡[1](WSN)由大量能夠進行無線通信的節點組成，在靜態WSN中，一旦部署了節點就幾乎不會移動.然而，在一些場景中，傳感器節點需要是動態的，即移動無線傳感器網絡(MWSN)[2].與靜態傳感器網絡相比，針對MWSN的研究仍非常有限.本質上，根據現有協議，MWSN是WSN和移動自組織網絡[3](MANET)的重合部分.MWSN的路由協議可分為2個范疇：層次式和平面式.層次式路由協議分配任務給不同節點，而在平面路由協議中所有節點執行相同任務[4].主動式MANET路由協議對于MWSN來說并不合適[5].在MWSN場景中，最常使用的是自組網請求式距離向量(AODV)路由協議[6]或其相似協議.Aronsky等[7]提出了以數據為中心的編織多路徑(DCBM).Salehi等[8]提出一種地理機會路由(GOR)[8].GOR不需要分配拓撲信息，這是因為節點將數據轉發給更靠近匯聚節點的網格而不是節點.然而，如果在預期網格中沒有節點得到傳輸，那么,數據會通過處于較近網格中的節點轉發[9].周穎芝[10]針對具有移動能力的Sink節點，解決Sink周圍傳感器節點能量瓶頸問題.Cakici等[11]提出移動自適應跨層路由(MACRO).根據反應式協議，通常路由的發現會導致初始延遲.然而，與主動式協議比較，該延遲相較于路由表的洪泛延遲非常小.因此，本文提出一種基于時分多址[12](TDMA)的主動式高動態傳感器路由協議.

1 提出的AHDSR協議

使用固定時隙分配的方式產生一種自由沖突的全局TDMA MAC層，而不需要任何動態調度.該方法會降低所需開銷和計算效率，并要求全局同步.Nedev[13]說明了可用方法的選擇，由于匯聚節點也分配到一個時隙，所以,可以向所有傳感器節點傳輸高功率網絡范圍信標.該信標可以提供同步和網絡范圍控制命令.在目標應用程序中，由于匯聚節點是具有大型電力供應的固定地面站，所以額外的動力開銷并不是大問題.

為了允許節點轉發從其他節點接收到的數據，一個數據包必須具有可變容量.數據包的容量表示為幀，幀數為數據包中可用數據域的數量.數據包結構顯示了2種幀數據包,如表1所示.表1中：n為節點數；F為幀數，規定了可以從其他節點同時轉發多少幀；Ldata為應用程序數據區域所需大小，規定每幀中的數據量，以及這些數據來自哪些傳感器、傳感器的地理坐標和節點的狀態信息;Lp為區域總大小.由表1可知：類型1(幀1)通常針對傳輸中的節點數據和協議開銷，并且包含4個領域；類型2(幀2)只有3個領域.根據所需幀的數量，節點可能根據需要重復類型2(幀2)的結構.

表1 AHDSR數據包結構Tab.1 Packet structure of AHDSR

如果節點有來自4節點的數據要轉發，就會用其擁有的數據滿足類型1(幀1)，然后4次重復類型2的幀結構，每增加一個，需要傳輸的額外數據段就進行一次.轉發節點IDs區域表明數據包中存在的哪個節點數據，是通過使用單一字節表示每個節點實現.如果第3個和第6個字節設置較高，表示數據包中含有2個額外的幀，分別包含來自節點3和節點6的數據.

為了計算最小容許時隙的長度，需要對節點傳輸的幀數設置上限.因為距離匯聚節點更近的節點將會需要更多空間，而距離較遠的節點需要的較少.然而，變化的拓撲結構意味著節點的需求會隨著時間變化.同樣，如果最大幀數太低，那么瓶頸作用將會導致數據丟失.如果數據包最大，尺寸太大，將會浪費寬帶.較大的時隙長度將會減少傳輸頻率，并節約能源.

為了確定恰當的幀數最大值，度量α表示為

式(1)中:n為網絡中的節點總數;F為一個數據包的最大幀容量;α值是對于給定n和F不會遭受瓶頸作用的可能拓撲結構的分數.

在一個具有5個節點的網絡中,有1 024種可能拓撲結構.其中，拓撲結構的數量為2n(n-1)/2,n為節點的總數.允許每個節點轉發各自數據和其他2個節點數據，使得幀容量為3.在1 024個可能拓撲結構中，有704個不會遭受瓶頸作用，通過公式計算獲得，即

即有1 024-704=320種可能拓撲結構，那么幀容量為3就不能滿足要求.該例子中α為0.687 5，即68.75%的拓撲結構將不會因為瓶頸作用而受到損失.用這種方式可以使用式(1)基于網絡中節點數量和給定可接受的α值選擇合適的F值.

在AHDSR中，每次傳輸都由所有傳輸節點的鄰節點接收，允許所有節點收集局部拓撲信息，即節點鄰居的跳躍總數.節點使用該信息確定各自跳躍數量，比其鄰居最低跳躍總數大1.所以，如果一個節點有3個鄰居，跳躍總數為2,4或5，那么,該節點將會設置跳躍總數為3.由于使用一種確定的整體TDMA方案，節點將在每次循環中獲得來自每個鄰居的單一傳輸.即節點可以每次循環更新跳躍總數，這將使梯度指標能夠在整個網絡中得到維持而不會泛濫.這大大降低了協議開銷，也是其最大的優勢.

AHDSR使用跳躍總數梯度執行盲轉發，一個節點的傳輸會被所有鄰居聽到,并且這些節點獨立決定是否應該轉發任何接收到的數據.即當節點聽到一個傳輸時，將比較傳輸節點和自己的跳躍總數.如果接收的跳躍總數低于自己的，那么,傳輸節點距離匯聚節點更近且該數據包可以忽略.如果接收的跳躍總數高于自己的，那么,該傳輸節點距離匯聚節點更遠，所以從數據包中提取該數據并儲存.如果接收的跳躍總數等于自己的，那么,該傳輸節點距離匯聚節點的距離與自己的相同，則從數據包中提取該數據，評估并且儲存或丟棄.

每個幀都有一個狀態，指定為優先狀態的幀即為優先幀，而沒有優先權的幀并沒有被丟棄，而認為是多樣性的數據.傳輸節點產生的幀自動認為是優先幀，而轉發的幀通過一種幀的優先位為其指定優先權.當一個節點為了傳輸而收集數據包時，首先,將用優先數據填充可用幀;然后，任何空的幀將會用多樣性數據填滿.這允許節點使用更多可用數據包的容量.通過廣播，接收器做出轉發幀的決定，由于對數據包進行了廣播所以多個節點都會接收到數據.這在本質上創建了一種多路徑的方案，其中，相同數據沿著多個路由轉發到匯聚節點.路由分集的使用提高了可靠性，這是因為如果一個路徑沒能送出一段數據，而其他路徑可能會成功送出.即網絡中將會創建多個數據復制，這可能造成堵塞.然而，這個的權衡是在成功送出數據的可能性增加的情況下進行.

為了允許協議保持最小內存需求并且處理高水平通信量而丟棄作廢的幀.即如果一個節點接收到兩段源自相同節點的數據，那么，就會忽略老的片段支持新的片段.如果一個節點接收的數據比已經在隊列中的數據老，那么，就認為接收的數據過期并且將其丟棄.

圖1 運行AHDSR協議的傳感器節點的流程圖Fig.1 Flow chart of sensor node when running AHDSR protocol

單一節點在每個時隙操作的流程圖，如圖1所示.節點確定當前時隙是否是其專用時隙，如果是，則編輯來自隊列幀及其自身數據的數據包.首先，儲存優先數據；然后，用多樣性數據填充剩余空間；最后，將數據包散播給任何處于傳輸半徑內的節點.

通常不是節點專用的時隙都需要偵聽數據包，節點在接收一個數據包時，會提取傳輸跳躍總數，且在需要時進行自我更新.恢復相關數據并儲存用于轉發.AHDSR分別對待每個節點，即不同幀可以采用多種不同路徑穿過網絡.同時，通過只共享拓撲信息意味著維持最小開銷，并且將梯度度量維持在高移動環境中.

2 仿真實驗與分析

利用OPNET建模[14]模塊進行仿真，提供了一種離散時間仿真器.傳輸半徑為250 m，收發器的傳輸速率為250 kbit·s-1.模仿一種低成本、低功率的收發器，節點移動性使用隨機路點模型控制，暫停時間設置為0，且通過0 m·s-1和最小值之間的均勻分布設置速度.所有節點包括匯聚節點都會移動.每個傳感器節點認為是一種資源，并且可以以這種速度產生數據.數據長度是一個固定參數，對于仿真32 bit，包含了節點的空間坐標和抽取的傳感器數據.為了表征不同參數下協議性能，采用平均端到端遲延(τ)、數據包投遞率(PDR)、吞吐量、開銷(B)和能量損耗(P)進行評估.

2.1不同節點最大速度

不同最大速度時，各路由協議的結果如圖2所示.圖2中：vmax為最大速度.節點數固定為25，每個節點的數據產生速率設定為1 pk·s-1(pk為數據包數目).同時，網絡大小為600 m×600 m.由圖2可知：隨著節點最大速度的增加，各個協議的PDR和吞吐量均呈下降趨勢，因為錯誤估計節點速度的增加會導致更多的數據包丟失，從而降低PDR.相比其他幾種協議，MACRO雖然具有較高的PDR，但其網絡吞吐量低于所提的AHDSR協議.

(a) PDR

(b) 平均端到端延遲 (c) 開銷

在PDR和吞吐量方面，DCBM和GOR的性能較差.DCBM和GOR較大的開銷是由路由發現和拓撲信息共享導致，同時也導致了網絡的堵塞，產生了較大延遲和數據包丟失.此外，仿真中增加速度意味著拓撲結構改變更加頻繁，因此，需要更大開銷來維持更新路由.開銷的分析結果非常接近AHDSR的仿真結果，即當速度增加時，兩種度量增幅最小.延遲結果在速度較高時增加較小，預期結果比仿真結果的延遲時間稍高.DCBM有最長的延遲時間，而GOR的平均延遲時間比AHDSR小.GOR的低PDR意味著丟棄了許多數據包，因此，網絡中有更少數據包，即傳送的數據包在網絡中的速度更快.MACRO比AHDSR顯示出稍好的延遲，但是，AHDSR提高了開銷水平且有更好的能量性能.通常DCBM和GOR在這些情景中的性能較差，這是因為其并不適用于這些較高速度的類型.而AHDSR和MACRO性能更好.

2.2不同流量負荷

不同流量負荷時，各路由協議的結果如圖3所示.圖3中：vp為數據包產生速度；節點數固定為25個；最大速度為25 m·s-1.每個傳感器節點都產生數據，全網流量負載為2.4～586.3 pk·s-1.最大產生速度24.4 pk·s-1表示最大允許數據傳輸速率.這是由TDMA循環的長度指示，由于一個節點值能夠在一次循環中傳輸一次，所以其最大數據產生速度為1/Δn，導致全網數據產生速度為1/Δ.

(a) PDR

(b) 平均端到端延遲 (c) 開銷

(d) 吞吐量 (e) 平均能量損耗圖3 不同流量負荷的各路由協議結果Fig.3 Result of each protocol with different traffic load

關于輻射映射應用，概念數據產生速度可以控制映射的分辨率.PDR通常較高且對于更高數據產生速率顯著增加，這種增加的結果是TDMA循環時間等于數據產生速度的倒數.在實踐中，通過均勻延遲完成每個時隙，即在較低數據包速率的情況下，循環時間很長，使梯度指標更新較慢.當數據產生速度為0.1 pk·s-1，循環時間為10 s，且平均鏈接壽命tav為12.73 s時，沒有定期更新梯度場.然而，由于0.5 pk·s-1的循環時間為2 s，所以只有一種可能具有較低數據產生速度，能夠在拓撲結構改變的情況下維持梯度場.通過延長時隙以適應所需數據生成率，從而節約能量.能量消耗結果顯示，當網絡中數據包增加時，平均能耗也會隨之增加.

相比之下，即使在較低的數據包速度下，DCBM和GOR也使用大量能量，當數據產生速度增加時，能量損耗稍有增加.在更高數據包速度下，MACRO能量損耗有所增加，然而，由于飽和在10 pk·s-1之后停滯，AHDSR分析結果稍微高估了能量增加.開銷結果顯示，DCBM和GOR即使在沒有太多數據輸送的情況下，也產生大量開銷，但是由于引進了更多數據，數據比特和開銷之間的比率均等.

AHDSR顯示了持續低量的開銷，通過分析結果近似預測.MACRO在開銷方面顯示了輕微增加，但是其吞吐量在數據包產生速度大于5 pk·s-1時，似乎達到了飽和限度.AHDSR吞吐量在數據產生速度增加時，平穩升高.DCBM和GOR的吞吐量在越來越多數據包丟失時開始進入穩定階段.延遲結果顯示，AHDSR持續較低延遲，實際上，當產生更多數據時減小.這是因為循環時間的減小，允許每個節點更頻繁地進入介質，所以數據包可能更快地穿過網絡.相比之下，MACRO在5 pk·s-1之后，其延長時間急速上升.總之，AHDSR在1 pk·s-1以上表現出持續較高的性能水平，其他3個協議當通信量水平增加時退化明顯.

實驗結果顯示，AHDSR適合于廣泛的場景，包括模擬具有UAV的輻射映射的應用.DCBM和GOR的結果在這些場景中的性能水平較低.與MACRO相比，AHDSR的能量損耗更大.然而，MACRO在一些場景中的PDR水平顯著提高.在延遲方面，AHDSR端到端延遲與MACRO相似.

3 結束語

提出一種針對MWSN設計的路由協議，AHDSR通過使用全局TDMA MAC層，降低開銷的方法維持梯度指標,并使用盲轉發技術，允許數據同時通過多路徑穿過網絡.該協議適用于各種高動態的數據網絡場景.仿真分析表明：該協議在各種不同移動性、延展性和通信量水平的情況下都有效，性能表現優異.由于節點能夠將數據從多個節點傳輸到單一數據包中，所以未來研究可能關注于使用聚合技術組合接收，進一步研究協議性能信道衰減的影響.

[1] 梁娟,吳媛.采用 WSVM 的三維無線傳感器網絡節點定位[J].華僑大學學報(自然科學版),2016,37(1):79-83.

[2] 馬睿.移動無線傳感器網絡路由協議的分析與研究[D].北京：北京郵電大學,2011:9-23.

[3] 吳大鵬,武穆清,甄巖.移動自組織網絡可用帶寬估計方法研究進展[J].通信學報,2010,31(4):103-115.

[4] 毛萬東.移動無線傳感器網絡節點定位技術研究[D].合肥：中國科學技術大學,2014:13-25.

[5] LAMBROU T P,PANAYIOTOU C G.A Survey on routing techniques supporting mobility in sensor networks [C]∥International Conference on Mobile Ad-hoc and Sensor Networks.Wuyishan:IEEE Press,2009:78-85.

[6] KOMATHY K,NARAYANASAMY P.Trust-based evolutionary game model assisting AODV routing against selfishness[J].Journal of Network and Computer Applications,2008,31(4):446-471.

[7] ARONSKY A,SEGALL A.A multipath routing algorithm for mobile wireless sensor networks[C]∥Wireless and Mobile Networking Conference.Budapest:IEEE Press,2010:1-6.

[8] SALEHI M,BOUKERCHE A.Trust-aware opportunistic routing protocol for wireless networks[C]∥Proceedings of the 10th ACM Symposium on QoS and Security for Wireless and Mobile Networks.New York:ACM,2014:79-86.

[9] 班冬松,溫俊,蔣杰,等.移動無線傳感器網絡k-柵欄覆蓋構建算法[J].軟件學報,2011,22(9):2089-2103.

[10] 周穎芝.移動無線傳感器網絡路由協議的研究[D].南京：南京郵電大學,2014:24-35.

[11] CAKICI S,ERTURK I,ATMACA S,etal.A novel cross-layer routing protocol for increasing packet transfer reliability in mobile sensor networks[J].Wireless Personal Communications,2014,77(3):2235-2254.

[12] 周得敏,劉蕓江,李曼,等.一種基于令牌的短波網動態TDMA協議設計與仿真[J].重慶郵電大學學報(自然科學版),2015,27(5):595-601.

[13] NEDEV M D.Time synchronization in sensor networks[J].Program Systems Institute of RAS,2011,37(4):71-84.

[14] 李曉汀,丁凡,熊華鋼.基于OPNET的CAN網絡建模與仿真[J].北京航空航天大學學報,2009,35(3):284-287.

(責任編輯： 黃曉楠英文審校： 吳逢鐵)

ActiveHighDynamicSensorRoutingProtocolUsingTimeDivisionMultipleAccess

ZHU Chaojun1,2

(1. College of Computer Science, Sichuan University, Chengdu 610000, China;2. Department of Judicial Information Management, Sichuan Judicial and Police Officers Professional College, Deyang 618000, China)

10.11830/ISSN.1000-5013.201605075

2016-05-23

朱超軍(1975-)，男，副教授，主要從事計算機網絡、網絡安全的研究.E-mail:zhuchaojunsc@126.com.

四川省科技支撐計劃項目 (2012GZ0091)

TP 393

A

1000-5013(2017)05-0710-06