3.4.2　基于分配的MAC協議

競爭型MAC協議可提高事件傳輸的實時性和帶寬的利用率，但隨著網絡負載流量的增加，控制分組與數據分組發生碰撞的概率也相應增加，從而使網絡發生擁塞，耗費大量能量。而基于分配的MAC協議采用TDMA、CDMA、FDMA或SDMA等技術，將一個物理信道劃分為多個子信道，然后將這些子信道劃分給需要發送數據的節點，從而避免產生沖突。以前的基于分配的MAC協議一般都沒有考慮到節省能量的問題，因此不適合用在無線傳感器網絡系統中。基于能量考慮，研究人員也提出了幾種適用于無線傳感器網絡的MAC協議，這些協議有一些共同的優點，如不存在沖突，沒有隱蔽終端等問題，容易進入睡眠狀態，尤其適合能量有限的無線傳感器網絡。下面介紹幾種經典的基于分配的無線傳感器網絡MAC協議。

1. SMACS協議

早在1999年，美國加州大學洛杉磯分校（UCLA）的研究人員就提出了一種自組織無線傳感器網絡協議架構，該架構針對規模龐大、節點移動性不強且能量有限的傳感器網絡應用設計了協議棧，其中包括SMACS協議。SMACS是一種分配的MAC協議，可以完成網絡的建立和通信鏈路的組織分配。在此基礎上，研究人員還提出了EAR算法，該算法實現了對網絡中緩慢移動節點的移動性管理，使移動節點和靜止節點之間實現無縫連接。通過在GloMoSim平臺上進行仿真，SMACS的性能得到了驗證。

1）基本思想

SMACS協議假設每個節點都能夠在多個載波頻點上進行切換，該協議將每個雙向信道定義為兩個時間段，這類似于TDMA機制中分配的時隙。SMACS協議是一種分布式協議，允許一個節點集發現鄰居并進行信道分配。傳統的鏈路分簇算法首先要在整個網絡執行鄰居發現的步驟，然后分配信道或時隙給相鄰節點之間的通信鏈路。SMACS協議在發現相鄰節點之間存在鏈路后立即分配信道，當所有節點都發現鄰居后這些節點就組成了互聯的網絡，網絡中的節點兩兩之間至少存在一個多跳路徑。由于鄰近節點分配的時隙有可能產生沖突，為了減少沖突的可能性，每個鏈路都分配一個隨機選擇的頻點，相鄰的鏈路都有不同的工作頻點。從這點上來講，SMACS協議結合了TDMA、FDMA的基本思想。當鏈路建立后，節點在分配的時隙中打開射頻部分，與鄰居進行通信，如果沒有數據收發，則關閉射頻部分進行睡眠，在其余時隙節點關閉射頻部分，降低能量損耗。

2）關鍵技術

（1）鏈路建立。SMACS協議引入了超幀的概念，用一個固定參數Tframe表示，網絡中所有節點的超幀都有相同的長度。節點在上電后先進行鄰居發現，每發現一個鄰居，這一對節點就形成一個雙向信道，即一個通信鏈路。在兩個節點的超幀中為該鏈路分配一對時隙用于雙向通信。隨著鄰居的增加，超幀慢慢地被填滿。每對時隙都會選擇一個隨機的頻點，減少鄰近鏈路沖突的可能。這樣全網很快就能在初始化建立鏈路，這種不同步的時隙分配被稱為異步分配通信，下面將對鏈路如何建立進行舉例說明。

異步通信分配機制如圖3.10所示，節點A和節點D分別在Ta和Td時刻開始進行鄰居發現，在發現過程完成后，兩個節點約定一對固定的時隙分別進行發送和接收。此后在周期性的超幀中此時隙固定不變。節點B和節點C分別在Tb和Tc時刻開始進行鄰居發現，執行上述同樣的步驟，由于時隙的約定彼此獨立，所以有可能發生重疊，如果各個時隙在同一頻點上就會發生沖突。圖3.10中如果節點D向節點A發送數據，和節點B向節點C發送數據在時間上有重疊，給兩個時隙分配不同的頻點，如分配fx給節點A、D，分配fy給節點B、C，就可以避免沖突。SMACS中每個節點有多個頻點可選，在建立鏈路時都要選擇一個隨機的頻點，這就大大減少了沖突發生的可能性。

（2）鄰居發現和信道分配。為了比較清楚地闡述SMACS協議中的鄰居發現機制，下面以舉例的形式來說明。如圖3.11所示，假設節點B、C、G進行鄰居發現。這些節點在隨機的時間段內打開射頻模塊，在一個固定的頻點監聽一個隨機長度的時間。如果在此監聽時間內節點沒有接收到其他節點發出的邀請消息，那么隨后節點將發送一個邀請消息。在圖3.11中，節點C就是在監聽結束后廣播的一個邀請消息Type1。節點B和節點G接收到節點C發出的Type1消息后，等待一個隨機的時間，然后各自廣播一個應答消息Type2。如果兩個應答消息不沖突，節點C將接收到節點B和節點G發來的邀請應答。節點C在這里進行一個選擇，可以選擇最早到達的應答者，也可以選擇接收信號強度最大的應答者。在選擇了應答者后，節點C將立即發送一個Type3消息通知哪個節點被選擇。此處選擇最早到達的節點B作為應答者，節點G將關閉射頻部分進入睡眠狀態，并在一個隨機的時間后重新進行鄰居發現。

如果節點C已經選擇了鄰居，將在消息Type3中攜帶分配信息，該信息包含節點C的下一個超幀的起始時間。在收到該分配消息后，節點B將和本地的超幀起始時間進行比較，得到一個時間偏移，并找出兩個共同的空閑時間段作為時隙對，分配給節點B和節點C之間的鏈路。在確定了時隙對后，節點B選擇一個隨機的頻點，將時隙對在超幀中的位置信息以及選擇的頻點通過消息Type4發送給節點C。經過這些測試信息的成功交換后，節點B和節點C之間就完成了時隙分配和頻率選擇。

在SMACS形成的網絡中，與超幀同步的節點組成一個子網，如圖3.10所示，節點A、節點D和節點B、節點C分別組成子網。隨著鄰居的增加，子網的規模會變大，并且會和其他子網的節點建立鏈路，實現整個網絡的無縫連接。兩個不同子網的節點在建立通信鏈路時，如果超幀有重疊的空閑時段，可以為新鏈路分配時隙，則可以成功建立鏈路；否則，節點只能放棄并尋找其他節點來建立鏈路。

3）算法描述

在靜態的MAC協議進行類似于TDMA幀結構的時隙分配時，靜止的節點需要周期地廣播邀請信息，這樣可以周期地進行鄰居發現，允許新節點加入網絡，使協議適應網絡拓撲的變化。邀請信息不需要在每個超幀廣播，每間隔固定個數的超幀再多進行一次廣播即可。移動節點偵聽這些邀請信息，所以這些邀請信息也可以作為移動節點的引導信號。移動節點根據這些引導信號決定最佳路線，所以SMACS協議將邀請信息作為EAR算法的觸發器。移動節點可以從邀請信息中獲得信噪比、節點地址、功率等信息。為了記錄相鄰節點的信息，移動節點都要保持一個鄰居記錄，每條記錄包含了建立、保持和取消一個通信鏈路所需要的信息。同樣地，靜止節點也要保存一個鄰居記錄，每條記錄只包含與該節點建立鏈路的移動節點的地址，如果鏈路取消，則需要刪除對應節點的記錄信息。建立和取消通信鏈路的過程由移動節點分配。

EAR算法定義了一種新的信令機制，主要使用以下4種消息：Broadcast Invite（BI），靜止節點邀請其他節點加入；Mobile Invite（MI），移動節點響應BI并請求建立連接；Mobile Response（MR），靜止節點取消連接，不需要響應；Mobile Disconnect（MD），移動節點取消連接。移動節點和靜止節點通過交換信令實現EAR算法的機制，也就是如何建立移動節點和靜止節點之間通信鏈路的機制。主要有以下步驟：

（1）靜止節點會每間隔固定個超幀發送一次BI消息，移動節點在接收到靜止節點的BI消息后將開始連接過程。首先，靜止節點被記錄，移動節點在接收BI消息時可以得到鏈路的質量，根據鏈路質量決定是否向靜止節點發起連接請求。如果不發起連接請求，相關的靜止節點信息只是簡單地保存在鄰居記錄中；如果發起連接請求，則移動節點回復一個MI消息，等待響應，同時繼續偵聽其他BI消息。移動節點如果接收到其他相鄰節點的BI信息，暫時將對應相鄰節點消息保存到鄰居記錄，如果直到記錄表被填滿的時候，還接收到新節點的BI信息，移動節點會將其鏈路質量（通過信道的SNR值大小判斷）和當前記錄表中最差鏈路質量相比較，決定是否替換相應的相鄰節點信息。

（2）靜止節點在接收到MI消息后需要檢查是否可以建立連接。如果可以建立，則靜止節點在TDMA幀中選擇可用的時隙，并回復一個確認信息給移動節點，表示接收建立連接請求。同時，靜止節點會記錄此移動節點的地址信息。如果沒有可用的時隙，則無法建立連接，靜止節點回復一個拒絕信息。所有的回復信息都包含在MR消息中。

（3）連接建立后，移動節點在移動過程中會接收到新的相鄰靜止節點發送的BI消息，移動節點會根據信道質量選擇淘汰相鄰節點記錄中連接質量較差的相鄰節點。如果移動節點在移動過程中遠離了已經建立連接的靜止節點，則連接質量將會下降，最后將被淘汰，這就需要取消已經建立的連接（發送MD消息）。決定是否取消和建立連接都需要根據相應的門限值，當一個已建立連接的信道SNR值低于取消連接門限值時，就需要發送MD消息給對應的靜止節點以取消連接。設置較大的建立連接門限值能提高網絡連接質量，但會減少網絡中的通信鏈路；設置較大的取消連接門限值能提高網絡的平均SNR值，但移動節點會更頻繁地取消連接，增加控制開銷產生的能量損耗。

SMACS協議提出了一種TDMA/FDMA相結合的信道分配機制，該協議不需要集中控制的算法，可用來建立一種平面結構的網絡。通過為每對時隙分配隨機的載波頻率，SMACS協議可避免全局時間同步，從而減少復雜性。通過在超幀分配的時隙進行睡眠，SMACS協議可減少空閑偵聽和串擾，提供較好的能量效率。通過引入EAR算法，SMACS協議對節點的移動性提供了一定的支持，但協議需要節點能提供多個載波頻點，對節點硬件提出了要求。此外，EAR算法收斂速度較慢，不適合移動性較強的應用。

2. TRAMA協議

TRAMA（Traffic Adaptive Medium Access，流量自適應媒體訪問）協議是較早提出的基于分配的WSN MAC協議，其基本思想源于NAMA協議，在NAMA協議的基礎上引入了睡眠機制，該協議的信道分配機制不僅能夠保證能量效率，而且對于帶寬利用率、延遲和公平性也有很好的支持。通過在QualNet平臺上的仿真，將TRAMA協議與S-MAC、NAMA等協議進行了分析比較。

1）基本思想

TRAMA協議采用了流量自適應的分布式選舉算法，節點交換兩跳內的鄰居信息，在傳輸分配時指明在時間順序上哪些節點是目的節點，然后選擇在每個時隙上的發送節點和接收節點。TRAMA協議由三部分組成，其中鄰居協議（Neighbor Protocol，NP）和分配交換協議（Schedule Exchange Protocol，SEP）允許節點交換兩跳內的鄰居信息和分配信息；自適應選舉算法（Adaptive Election Algorithm，AEA）利用鄰居和分配信息選擇當前時隙的發送者和接收者，讓其他與此次通信無關的節點進入睡眠狀態以節省能量。

TRAMA協議將一個物理信道分成多個時隙，通過對這些時隙的復用為數據和控制信息提供信道。圖3.12所示為TRAMA協議信道的時隙分配情況。每個時間幀分為隨機接入和分配接入兩部分，隨機接入時隙也稱為信令時隙，分配接入時隙也稱為傳輸時隙。由于無線傳感器網絡傳輸速率普遍較低，所以對于時隙的劃分以毫秒為單位。傳輸時隙的長度是固定的，可根據物理信道帶寬和數據包長度計算得出。由于控制信息量通常比數據信息量要小得多，所以傳輸時隙通常為信令時隙的整數倍，以便于同步。

2）關鍵技術

（1）鄰居協議（NP）。在無線傳感器網絡中，由于節點失效或者新節點加入等現象存在，網絡拓撲在動態地變化，TRAMA協議需要適應這種變化。在TRAMA協議中，節點啟動后處于隨機接入時隙，在此時隙內節點為接收狀態，可以選擇一個隨機時隙發送指令。隨機接入時隙的長度選擇可根據應用來決定，如果網絡移動性不強，拓撲相對穩定，則該時隙較短；否則就需要適當延長該時隙，但該時隙的延長會增加空閑偵聽的能量損耗，降低網絡的能量效率。節點之間的時鐘同步信息也是在隨機接入時隙中發送的。由于在隨機接入時隙中各個節點都可以選擇隨機接入時隙進行發送，控制信息有可能發生碰撞而丟失，為了減少碰撞，隨機接入時隙的長度和控制信息的重傳次數都要進行相應的設置。對于一個有N個兩跳鄰居的節點，當控制信息的重傳次數為7且重傳間隔為1.44N時能保證99%的成功率，因此隨機接入時隙的長度可設置為7×1.44×N。

通過在隨機接入時隙中交換控制信息，鄰居協議實現了相鄰節點信息的交互。圖3.13所示為控制信息幀的幀頭格式。控制信息中攜帶了增加的鄰居的更新，如果沒有更新，控制信息作為通知鄰居自己存在的信標。每個節點發送關于自己下一跳鄰居的增加更新，用來保持鄰居之間的連通性。如果一個節點在一段時間內都沒有再收到某個鄰居的信標，則該鄰居失效。由于節點知道下一跳鄰居和這些鄰居的下一跳鄰居的信息，所以網絡中每個節點都能交換兩跳鄰居信息。

（2）分配交換協議（SEP）。分配交換協議用于建立和維護發送者與接收者選擇時隙需要的分配信息。首先每個節點生成分配信息，然后通過廣播實現分配信息交換和維護。

分配信息生成的過程為，節點根據高層應用產生數據的速率計算出一個分配間隔SCHEDULE_INTRVAL，該間隔代表了節點能夠廣播分配信息給相鄰節點的時隙個數，然后在[t，t+SCHDULE_INTRVAL]內，節點計算在其兩跳鄰居范圍內具有最高發送優先級的時隙數，這些時隙稱為贏時隙。由于在這些時隙中節點可能被選為發送者，故節點需要通知這些時隙中數據的接收者。當然，如果節點沒有帶發送的數據，也需要通知鄰居它將放棄相關時隙，其他需要發送數據的節點可以使用這些空閑時隙。在一個分配間隔內最后一個置1的贏時隙稱為變更時隙，用于廣播節點下一次分配間隔內的時隙分配情況。

節點通過分配幀廣播分配信息，其過程為節點通過鄰居協議獲得兩跳鄰居信息，分配幀不需要指定目的地址，通過位圖來指定接收者。位圖中每一位對應一個一跳相鄰節點，位圖的長度等于節點的一跳鄰居數，需要該節點接收數據則將對應位設置為1，這樣可以方便地實現單播、組播和廣播。節點根據當前的贏時隙分布形成位圖，將沒有數據要發送的贏時隙對應位設置為0，否則設置為1。圖3.14所示為分配幀格式，其中SourceAddr是發送分配幀的節點地址，Timeout是從當前時隙開始本次分配有效的時隙數，Width是鄰居位圖長度，NumSlots是總的贏時隙數。

此外，節點采用攜帶機制，在每個節點的數據包中都攜帶有節點的分配摘要，如圖3.14所示，減少廣播沖突對分配交換的影響。分配摘要帶有該分配的Timeout、NumSlots和位圖信息。

節點需要維護下一跳鄰居的分配信息，過程為分配信息的交換通過分配摘要來完成，如果節點不是數據的目標，那么節點的分配處于不同步狀態，直到節點根據發送者發來數據中的分配摘要更新分配。

3）算法描述

為了提高能量效率，TRAMA盡可能地讓節點處于睡眠狀態，通過重用已經分配但未使用的時隙來提高帶寬利用率。在分配接入周期任意一個給定的時隙t中，所有節點的狀態是由該節點的兩跳鄰居信息和該節點的一跳鄰居發布的分配信息來確定的，有發送、接收、睡眠三種狀態。

在相關文獻提出的NCR算法中，如果節點在其競爭集中有最高的優先級，則選擇該節點作為發送者。節點u的競爭集是節點所有兩跳鄰居的集合，節點u在時隙t的優先級定義為一個偽隨機hash函數，由節點的地址u和時隙t共同決定，即prio(u, t)=hash(u⊕t)。在任意一個給定的時隙，節點u處于發送狀態只有兩種可能：節點u有最高優先級或節點u有數據要發送。當節點處于接收狀態時，節點是當前某個發送者的目標節點，否則節點就進入睡眠狀態。每個節點通過AEA算法來確定當前應處于何種狀態。AEA算法的偽碼描述如圖3.15所示，表3.1列出了AEA算法描述中一些基本術語和符號。

TRAMA協議是一種基于分配的MAC協議，節點通過鄰居協議獲得鄰居信息，通過SEP協議建立和維護分配信息，通過AEA算法分配時隙給發送節點和接收節點。TRAMA協議在沖突避免、時延、帶寬利用率等方面都能提供較好的性能，但協議需要較大的存儲空間來存儲兩跳鄰居信息和分配信息，需要運行AEA算法，復雜度較高。由于AEA算法更適合于周期性的數據采集任務，所以TRAMA協議通常適合周期性監測應用。