王 宇，朱益鋒，趙增華

（天津大學計算機科學與技術學院，天津300072）

1 概述

互聯(lián)網(wǎng)的普及和應用不僅給人類生活帶來了便利，而且正改變著人類的生活習慣和生活方式，極大促進了人類社會的發(fā)展。然而，大部分居住在發(fā)展中國家貧困農村和發(fā)達國家偏遠地區(qū)的人們，由于有線網(wǎng)絡設備部署和維護費用高等原因，一直沒有享受到快速和穩(wěn)定的網(wǎng)絡服務。基于IEEE802．11的長距離無線 Mesh網(wǎng)絡（Long－distance Wireless Mesh Network，LDmesh）是指相鄰節(jié)點間距離很長（幾十甚至上百公里）的新型網(wǎng)絡，其中的工作節(jié)點通常配置高增益無線保真（Wireless Fidelity，WiFi）定向天線以達到長距離的信號覆蓋［1］。LDmesh網(wǎng)絡與傳統(tǒng)的有線網(wǎng)絡相比，具有搭建成本低、覆蓋范圍廣、易于部署和維護等特點，適用于地廣人稀的區(qū)域或偏僻落后的農村。由此可見，研究長距離無線Mesh網(wǎng)絡，對促進社會和經(jīng)濟發(fā)展具有重要的意義。

在長距離無線Mesh網(wǎng)絡中對媒體訪問控制（Media Access Control，MAC）協(xié)議的研究和設計一直都是核心問題。文獻［2］將低成本的網(wǎng)絡設備引入長距離無線Mesh網(wǎng)絡，文獻［3－4］利用實驗設備分別在高密度和低密度人口地區(qū)進行測試和應用。文獻［5－7］設計和應用分時MAC協(xié)議，對長距離無線Mesh網(wǎng)絡的性能進行評估。傳統(tǒng)基于IEEE 802．11的MAC協(xié)議是針對小范圍移動網(wǎng)絡而提出。LDmesh網(wǎng)絡雖然與傳統(tǒng)無線局域網(wǎng)（Wireless Local Area Network，WLAN）一樣都是使用IEEE 802．11無線網(wǎng)卡，但是與傳統(tǒng) WLAN相比，長距離的單跳傳輸距離特點使得IEEE 802．11中常用的網(wǎng)絡協(xié)議和機制效率低下，如采用自動重傳（Automatic Repeat Requset，ARQ）。 因 此，在LDmesh網(wǎng)絡中，需要重新設計MAC協(xié)議來提升網(wǎng)絡性能。

針對LDmesh網(wǎng)絡中MAC協(xié)議的設計，國內外研究人員提出多種設計方案。文獻［8］給出SynOp概念，在分析其可行性后，提出2PMAC協(xié)議［9］，并在實驗床上進行系統(tǒng)研究，奠定了長距離無線Mesh網(wǎng)絡MAC協(xié)議研究的基礎，為該領域研究提供了良好的理論基礎。文獻［10－12］針對2PMAC協(xié)議的不足，結合實際情況對2PMAC協(xié)議進行改進，提出自適應時隙的MAC協(xié)議，克服了外部環(huán)境的干擾，使其能更好地應用于長距離無線Mesh網(wǎng)絡。這些協(xié)議能優(yōu)化長距離無線Mesh網(wǎng)絡的性能，為長距離無線Mesh網(wǎng)絡的應用提供技術支持。但當前協(xié)議都使用信令包（如Marker包或Token包）來實現(xiàn)不同節(jié)點間以及同一節(jié)點不同接口間的同步，一旦用于同步的信令包丟失則會導致MAC協(xié)議失效，重新同步需要很長時間來恢復網(wǎng)絡，從而導致網(wǎng)絡性能低下。

因此，在長距離無線Mesh網(wǎng)絡中設計一種簡單易行的時隙同步MAC協(xié)議十分必要?？紤]到目前衛(wèi)星授時功能的廣泛應用，本文在長距離無線Mesh網(wǎng)絡MAC協(xié)議中引入衛(wèi)星授時技術，提出基于GPS衛(wèi)星授時的TDMA MAC協(xié)議GT－MAC，利用GPS衛(wèi)星的秒脈沖信號中的精準時鐘信息來實現(xiàn)不同節(jié)點間及同一節(jié)點不同接口間的同步。本文使用的實驗平臺為自主研發(fā)的 WiZiTJU－GPS，能夠獲取GPS衛(wèi)星秒脈沖信號并更新節(jié)點時間，改進網(wǎng)卡驅動Madwifi，并通過實驗對GT－MAC協(xié)議性能進行評估。

2 GT－MAC協(xié)議設計

GT－MAC協(xié)議采用2PMAC協(xié)議提出的SynOp思想［8］，通過控制網(wǎng)絡中節(jié)點的統(tǒng)一接收或發(fā)送，避免接口間的相互干擾，即節(jié)點的全部接口同時處于發(fā)送（Tx）或接收（Rx）狀態(tài)，若一個接口轉換狀態(tài)，則它的全部對應鄰居接口也相應轉換狀態(tài)。

2．1 GT－MAC時隙調度

如圖1所示，節(jié)點首先在初始時刻分配一個初始狀態(tài)。在Tx狀態(tài)下，節(jié)點發(fā)送數(shù)據(jù)包（如果需要發(fā)送）直到下一個時隙到來，然后切換至Rx狀態(tài)；而在Rx狀態(tài)下，節(jié)點被動接收數(shù)據(jù)包直到下一個時隙到來，然后切換至Tx狀態(tài)。

圖1 GT－MAC協(xié)議的節(jié)點時隙狀態(tài)切換

2．2 鄰居節(jié)點及接口的時隙同步

當進行GT－MAC協(xié)議的設計時，首先要保證各節(jié)點以及同一節(jié)點的各接口間的時隙同步，從而使整個網(wǎng)絡進行正確的時隙調度。

GT－MAC協(xié)議使用GPS衛(wèi)星授時進行同步。在每個節(jié)點部署具有授時功能的衛(wèi)星定位模塊，用于接收GPS秒脈沖來實現(xiàn)各個節(jié)點間、同一節(jié)點的不同接口間的時鐘同步。圖2描述了GT－MAC鄰居接口的時隙同步原理。

圖2 GT－MAC鄰居接口的時隙同步

網(wǎng)絡中所有節(jié)點工作在同一個信道，為避免相鄰鏈路間的干擾，需要采用2個狀態(tài)（發(fā)送／接收狀態(tài)）的工作方式，同一節(jié)點中所有接口的狀態(tài)相同，與其相鄰節(jié)點的狀態(tài)不同。也就是說，一個節(jié)點的各個接口如果處于發(fā)送狀態(tài)，與其相鄰的節(jié)點的各個接口必須都處于接收狀態(tài)；反之亦然。基于這個特點，要求網(wǎng)絡拓撲結構為二分圖。

假定網(wǎng)絡在構建時已經(jīng)具有二分圖拓撲結構，即節(jié)點分為2個互不相交的集合A和B，若一個節(jié)點在集合A中，則它的所有鄰居節(jié)點都在集合B中。假定所有節(jié)點事先配置好所屬集合。接收／發(fā)送的時隙長度相同，且設為固定值Ts，通常為20 ms。這樣1s就可以分成n個時隙，其中：

本文選擇適當?shù)腡s，使得n為整數(shù)。為簡單起見，n為偶數(shù)值。規(guī)定屬于集合A的節(jié)點在奇數(shù)時隙（第1個，第3個，第5個，…，第n-1個時隙）處于發(fā)送狀態(tài)，在偶數(shù)時隙（第2個，第4個，第6個，…，第n個時隙）處于接收狀態(tài)。屬于集合B的節(jié)點在奇數(shù)時隙處于接收狀態(tài)，在偶數(shù)時隙處于發(fā)送狀態(tài)。

基于GPS衛(wèi)星授時的TDMA MAC協(xié)議GTMAC運行在無線路由器中，網(wǎng)絡中的每個節(jié)點均是配備衛(wèi)星授時功能的無線路由器。圖3是長距離無線Mesh網(wǎng)絡一個典型的網(wǎng)絡拓撲圖。在網(wǎng)絡初始化階段，各節(jié)點首先通過衛(wèi)星定位模塊同步自身的時鐘，Tx時隙和Rx時隙長度都設置為20ms。網(wǎng)絡已經(jīng)具有二分圖拓撲結構，節(jié)點2、節(jié)點6、節(jié)點7、節(jié)點8組成獨立集A，其中的各節(jié)點所有接口的狀態(tài)設定：在每秒開始的奇數(shù)時隙為Tx，偶數(shù)時隙為Rx。節(jié)點1、節(jié)點3、節(jié)點4、節(jié)點5、節(jié)點9構成獨立集B，其中的各節(jié)點所有接口的狀態(tài)設定：在每秒開始的奇數(shù)時隙為Rx，偶數(shù)時隙為Tx。

圖3 長距離無線Mesh網(wǎng)絡中的典型網(wǎng)絡拓撲

2．3 累積反饋的可靠傳輸機制

雖然在上述2個狀態(tài)TDMA調度機制下，不會產生鏈路間信號干擾，但是長距離無線鏈路容易受到外部干擾或者信號傳輸衰落的影響而造成丟包。另外，在一個發(fā)送時隙通常能發(fā)送多個數(shù)據(jù)包，但由于長距離無線網(wǎng)絡的往返時延（Round－trip Time，RTT）較大，要盡量減少反饋（Acknowledgement，ACK）的發(fā)送，以提高信道利用率。鑒于此，本文通過改進網(wǎng)卡驅動Madwifi，設計累積ACK的可靠傳輸機制以提高傳輸可靠性和效率。

3 GT－MAC協(xié)議實現(xiàn)

3．1 GT－MAC協(xié)議授時功能實現(xiàn)

3．1．1 授時實驗平臺 WiZiTJU－GPS的搭建

GT－MAC協(xié)議的實驗平臺 WiZiTJU－GPS是基于天津大學計算機網(wǎng)絡實驗室自主研發(fā)的WiZiTJU嵌入式開發(fā)平臺［13］。WiZiTJU嵌入式開發(fā)平臺主要的軟硬件參數(shù)如表1所示。通過WiZiTJU的串口獲取GPS衛(wèi)星的秒脈沖信號，從中解析出時鐘信息，并使用該時鐘信息來實現(xiàn)各個節(jié)點及各節(jié)點接口間的同步。

表1 WiZiTJU嵌入式開發(fā)平臺的軟硬件參數(shù)配置

在WiZiTJU平臺的基礎上，采用的GPS模塊，即Trimble公司生產的Resolution T GPS授時接收機，如圖4所示。Resolution T GPS授時接收機是全功能的、具有12信道、并行跟蹤的嵌入式授時板，工作在L1（1 575．42 MHz）頻率，能夠為很多授時應用提供精確的GPS或UTC時鐘或同步。通過WiZiTJU－GPS的串口獲取GPS模塊產生的高精度時鐘信息（秒脈沖（Pulses Per Second，PPS）），并使用該時鐘信息來實現(xiàn)各個節(jié)點及各節(jié)點接口間的同步。實驗平臺WiZiTJUGPS的硬件架構如圖5所示。

3．1．2 WiZiTJU－GPS授時的實現(xiàn)

圖6描述了WiZiTJU－GPS上授時功能的設計思路。程序共分為兩部分：一部分是GPS秒脈沖觸發(fā)中斷模塊，其在內核態(tài)中執(zhí)行；另一部分是讀取串口中GPS時鐘信息并更新系統(tǒng)時間程序，其在用戶態(tài)中執(zhí)行。

圖6 WiziTJU－GPS授時功能設計

GPS秒脈沖觸發(fā)硬中斷，首先注冊中斷，使用WiZiTJU－GPS實驗平臺通用輸入／輸出（General Purpose Input Output，GPIO）的PC7引腳，注冊中斷號58，這里采用反相器把上升沿觸發(fā)中斷轉換為下降沿觸發(fā)中斷，保證秒脈沖信號精度。每當PC7引腳捕獲到GPS秒脈沖中斷信號后，產生硬件中斷，調用中斷服務程序。此時，中斷服務程序向用戶態(tài)程序發(fā)送信號。同時在獲取時間信息并更新系統(tǒng)時間程序中，首先在獲得GPS秒脈沖信號之前進行串口配置，之后等待來自內核態(tài)發(fā)來的信號。一旦收到來自內核態(tài)發(fā)來的信號，程序進入信號處理函數(shù)。在該函數(shù)中，首先讀取串口數(shù)據(jù)，然后根據(jù)Trimble公司標準接口協(xié)議（Trimble Standard Interface Protocol，TSIP）［14－15］對數(shù)據(jù)進行解析，獲取時間信息后更新系統(tǒng)時間。

3．2 改進網(wǎng)卡驅動Madwifi的GT－MAC協(xié)議實現(xiàn)

GT－MAC協(xié)議采用TDMA的方式進行數(shù)據(jù)發(fā)送和接收，每個時隙處于一個狀態(tài)（發(fā)送／接收），待下一個時隙開始與相鄰的節(jié)點同時互換狀態(tài)。該方式與原有的Madwifi設計不同，因此，需要對網(wǎng)卡驅動進行改進，以滿足GT－MAC的設計需要。

在Madwifi中，采用載波偵聽多路訪問／碰撞避免（Carrier Sense Multiple Access with Collision Avoidance，CSMA／CA）機制來避免沖突。節(jié)點在發(fā)送數(shù)據(jù)之前，先對鏈路進行監(jiān)聽，當空閑一段時間后，發(fā)送端根據(jù)指數(shù)退避算法選擇隨機等待時間開始退避，退避結束后直接發(fā)送數(shù)據(jù)。為了使CSMA／CA更加可靠，在MAC層增加了ACK機制。接收節(jié)點接收到數(shù)據(jù)包后，首先進行循環(huán)冗余校驗碼（Cyclical Redundancy Check，CRC）校驗，如果校驗正確則向發(fā)送節(jié)點回復一個ACK，對收到的數(shù)據(jù)包進行確認，發(fā)送節(jié)點收到該ACK后才繼續(xù)發(fā)送下一個包。IEEE 802．11協(xié)議使用請求發(fā)送／清除發(fā)送（Ready to Send／Clear to Send，RTS／CTS）機制來解決隱藏終端引起的沖突問題。發(fā)送節(jié)點在發(fā)送數(shù)據(jù)幀之前先發(fā)送RTS，若信道空閑，則目的節(jié)點發(fā)送CTS，允許發(fā)包。因此，結合GT－MAC的功能，對Madwifi進行以下改進：

（1）禁用 ACK，CSMA／CA，RTS／CTS。驅動中的ACK，CSMA／CA 的功能是在硬件抽象層（Hardware Abstraction Layer，HAL）和硬件中實現(xiàn)。通過把網(wǎng)卡中地址為0x8048的寄存器的第2位置1，來關閉ACK。通過提高網(wǎng)卡的監(jiān)聽閾值，縮小短幀間隙（Short Interframe Space，SIFS）、分布式幀間間隙（Distributed Inter－frame Spacing，DIFS）和退避時間slot＿time的值，綜合使用禁用隊列退避的3個方法來關閉 CSMA／CA 功能；最后使用iwconfig命令來關閉RTS／CTS功能。

（2）完善ath＿softc結構。這個數(shù)據(jù)結構中保存著網(wǎng)卡各種配置信息。為了設置GT－MAC協(xié)議中的固定時隙切換，需要在ath＿softc結構中添加時隙狀態(tài)和固定時隙計時器等數(shù)據(jù)成員，用于判斷和轉換時隙。

（3）在MAC層定義累積ACK：當接收時隙結束時，節(jié)點切換到發(fā)送時隙，同時發(fā)送一個累計ACK，對接收時隙接收的數(shù)據(jù)包進行確認。

（4）在 MAC層上增加邏輯鏈路控制（Logical Link Control，LLC）層。LLC層的作用是維護2個邏輯隊列：發(fā)送隊列和接收隊列。文獻［16］發(fā)送數(shù)據(jù)時先要把數(shù)據(jù)包添加到邏輯發(fā)送隊列，等到節(jié)點切換到發(fā)送時隙時，再將發(fā)送隊列中的數(shù)據(jù)包添加到硬件發(fā)送隊列中進行發(fā)送。當節(jié)點處于接收時隙時，先把接收到的包放入接收隊列，等到切換到發(fā)送狀態(tài)后，對上一個時隙接收到的數(shù)據(jù)包進行確認，將累計ACK發(fā)給發(fā)送節(jié)點，再將接收隊列中的數(shù)據(jù)包交給上層。

通過以上對Madwifi的改進，不僅提升了MAC協(xié)議在長距離中的性能，同時實現(xiàn)GT－MAC協(xié)議的固定時隙切換策略和累積ACK的可靠確認機制，從而產生能夠在 WiZiTJU－GPS實驗平臺上運行的GT－MAC協(xié)議。

4 實驗結果與分析

4．1 GT－MAC時隙同步驗證

實驗使用 WiZiTJU－GPS平臺運行GT－MAC協(xié)議，記錄2個對應節(jié)點a和b的時隙切換時間，通過對比驗證GT－MAC協(xié)議節(jié)點時隙調度策略的可行性。

隨機選取某時間段內10個連續(xù)時隙內的兩節(jié)點切換時隙時間，如圖7所示，2個節(jié)點均可保證每20ms切換時隙狀態(tài)，記錄的切換時隙的時間對應，誤差小于0．5ms，表明時隙調度策略能夠保證節(jié)點間時隙狀態(tài)相對應。

圖7 GT－MAC協(xié)議節(jié)點a，b對應的時隙切換時間對比

通過實驗可以看出，GT－MAC在2個節(jié)點上運行時，每個節(jié)點都可以獨立進行時隙調度，且2個節(jié)點均可保證每20ms切換時隙狀態(tài)，2個節(jié)點彼此時隙狀態(tài)對應較好、誤差較小。綜上所述，GT－MAC協(xié)議的時隙調度策略可行，能夠滿足2個節(jié)點時隙狀態(tài)的周期性切換，使得節(jié)點時隙的發(fā)送和接收狀態(tài)在一定程度上的對應。

4．2 GT－MAC性能評估

在20km的長鏈路上，如圖8所示（圖中天津理工大學新校區(qū)簡稱為“理工新校區(qū)”，是天津大學仁愛學院簡稱為“仁愛”），采用高增益的定向天線，如圖9所示。在鏈路兩端使用WiZiTJU－GPS實驗平臺，分別運行2PMAC協(xié)議和GT－MAC協(xié)議，在2個對應節(jié)點上分別運行Iperf進行實驗，實驗參數(shù)如表2所示，鏈路單跳吞吐率對比如圖10所示。

表2 GT－MAC性能參數(shù)

圖10 2PMAC和GT－MAC的吞吐率對比

通過實驗可以看出，2PMAC和GT－MAC的單跳吞吐率分別為 3．47Mb／s和 3．82Mb／s，GTMAC提升約10．1%，GT－MAC在長距離鏈路有更好的適應性。但采用2種協(xié)議下鏈路的整體吞吐率都不高，造成這種現(xiàn)象的原因主要是由于WiZiTJUGPS實驗平臺自身時鐘精度不高，不同節(jié)點的時鐘走勢不同且有時會有跳躍，盡管每個節(jié)點的時隙調度策略正確且能正常工作，但是仍舊無法實現(xiàn)不同節(jié)點間的時隙同步，一旦長時間運行就會導致誤差積累，從而導致整體吞吐率不高。

5 結束語

本文針對長距離無線Mesh網(wǎng)絡中信令包丟失降低網(wǎng)絡性能的問題，提出GT－MAC協(xié)議，使用GPS衛(wèi)星的秒脈沖信號對節(jié)點進行硬同步。首先搭建WiZiTJU－GPS硬件實驗平臺，利用硬中斷的方式接收秒脈沖信號，同時對系統(tǒng)時間進行更新，完成同步。然后對網(wǎng)卡驅動Madwifi進行修改，使節(jié)點的時隙狀態(tài)能夠周期性切換，同時實現(xiàn)了累積ACK的可靠確認機制。最后通過在長距離鏈路上的實驗，證明了GT－MAC協(xié)議比傳統(tǒng)2P MAC協(xié)議有更好的吞吐率，說明GT－MAC協(xié)議在長距離無線Mesh中有較好的適應性。由于本文設計的WiZiTJU－GPS實驗平臺在接收GPS衛(wèi)星秒脈沖信號時，能獲取高精度的時間信息及地理位置信息，因此可以利用地理位置信息確定節(jié)點位置，為進一步研究基于集中式節(jié)點管理的控制系統(tǒng)提供技術支持。

［1］趙增華，王 楠，竇志斌，等．基于IEEE 802．11的長距離無線 Mesh網(wǎng)絡［J］．計算機學報，2012，35（6）：1209－1222．

［2］Surana S，Patra R，Nedevschi S，et al．Beyond Pilots：Keeping Rural Wireless Networks Alive ［C］／／Proceed－ings of NSDI’08．San Francisco，USA：USENIX Association，2008：119－132．

［3］Subramanian L，Surana S，Patra R，et al．Rethinking Wireless for the Developing World［EB／OL］．（2014－07－16）．http：／／tier．cs．berkeley．edu／docs／wireless／large＿wild．pdf．

［4］Raman B，Chebrolu K．Experiences in Using WiFi for Rural Internet in India［J］．IEEE Communications Magazine，2007，45（1）：104－110．

［5］Paul K，Varghese A，Iyer S，et al．WiFiRe：Rural Area Broadband Access Using the WiFi PHY and a Multisector TDD MAC［J］．IEEE Communications Magazine，2007，45（1）：111－119．

［6］Dhekne A，Uchat N，Raman B．Implementation and Evaluation of a TDMA MAC for Wifi－based Rural Mesh Networks［C］／／Proceedings of iSoSP Workshop on Net－work System for Developing Regions．Washington D．C．，USA：IEEE Press，2009：124－137．

［7］Partha D，Vivek M，Debmalya P，et al．Joint Routing and Scheduling in Wireless Mesh Networks with Directional Antennas ［C ］／／Proceedings of International Conference on Computer Communications．Washington D．C．，USA：IEEE Press，2010：491－495．

［8］Bhaskaran R．Channel Allocation in 802．11－based Mesh Networks［C］／／Proceedings of International Conference on Computer Communications．Washington D．C．，USA：IEEE Press，2006：1－10．

［9］Bhaskaran R，Kameswari C．Design and Evaluation of a New MAC Protocol for Long Distance 802．11Mesh Networks［C］／／Proceedings of Annual International Conference on Mobile Computing and Networking．New York，USA：ACM Press，2005：156－169．

［10］Rabin P，Sergiu N，Sonesh S，et al．WiLDNet：Design and Implementation of High Performance Wi－Fi Based Long Distance Networks ［C ］／／Proceedings of Network－ed System Design and Implementation．Washington D．C．，USA：IEEE Press，2007：87－100．

［11］Nedevschi S，Patra R，Surana S，et al．An Adaptive，High－performance MAC for Long－distance Multihop Wireless Networks［C］／／Proceedings of Annual International Conference on Mobile Computing and Networking．New York，USA：ACM Press，2008：259－270．

［12］Yahel B D，Matthias V，Seth F，et al．JaldiMAC：Taking the Distance Further［C］／／Proceedings of Workshop on Network System for Developing Regions．New York，USA：ACM Press，2010：2－7．

［13］韓雙立，張力晨，周文濤，等．基于WIFI和Zigbee的無線網(wǎng)絡設備：中國，200910068172．1［P］．2009－08－19．

［14］Trimble Navigation Limited．TSIP Application Developer’s Guide：Revision A［M］．［S．l．］：Trimble Navigation Limited，2005．

［15］Xue Yanrong，Li Xiaohui．GPS Time System and Its Application in Time Transfer Technology［J］．Applied Mechanics and Materials，2013，401－403：1872－1878．

［16］王 楠．長距離無線 Mesh網(wǎng)絡2PMAC協(xié)議的實驗研究［D］．天津：天津大學，2011．