一種分布式的基于預留的多信道MAC協議

甄 雪，張閃閃

(曲阜師范大學 信息科學與工程學院，山東 日照 276826)

0 引 言

無線傳感器網絡的研究進展使得人們能夠更好地認識物理世界。由于數據匯聚的存在，傳感器網絡可以支持許多應用，包括安全監視[1]、定位[2]等。文中考慮的是靜態傳感器網絡中的周期性數據匯聚。在靜態的傳感器網絡中，通常建立一棵最優的數據匯聚樹收集網絡中的數據，其中數據匯聚樹是固定的，并且將數據傳輸到固定的匯聚節點[3-4]。

2008年，Mo等研究發現并行約會協議比單約會協議實現的效果更好[5]。2011年，Almotairi等提出了一種具有跳躍預留的多信道MAC協議[6]。2012年，Chang等提出了一種ECU-MAC協議，它可以同時提高信道利用率和增大網絡吞吐量[7]。2014年，Zhang等設計了一種FD-MMAC協議，結合一套先進的PHY-層技術，利用全雙工通信中的研究進展協調信道訪問[8]。2015年，Khanian等提出了一種分布式機會媒體接入控制(MAC)方法，可以最大化多信道無線網絡中預期的總吞吐量[9]。2016年，Zhuo等提出了iQueue-MAC，其中混合利用了CSMA和TDMA機制，降低了數據包的時延并增大了吞吐量[10]。2017年，Swain等提出了一種高效節能的多信道MAC協議，使節點能夠動態地在信道間進行切換[11]。

1 網絡模型

給定一棵基于樹型的網絡拓撲[12-13]，其中只有一個匯聚節點，有多個傳感器節點和中繼節點，傳感器節點收集周期性數據流，并以多對一和多跳通信的方式將數據傳輸到匯聚節點[14-15]，如圖1所示。另外，所有節點都具有單個半雙工無線電接口[16]。可以看出每跳的傳輸時延都將影響數據包到達匯聚節點的整體時延，因此，要想降低時延，則應該考慮降低每一跳的傳輸時延。另外，也可以看到每個節點可能有多個孩子節點，那么就會存在多發送端單接收端問題，容易造成沖突，因此還要考慮解決沖突的機制。

圖1 傳感器網絡

2 最佳信道的選擇

假設網絡中有多個信道，n是信道數量。在無線傳感器網絡中的數據傳輸之前，每個節點嘗試以不同的傳輸功率在每個信道上向父節點傳輸一個消息，父節點記錄每個消息的接收信號強度指示值并將其回復給孩子節點。

ri(pj)=ai·pj+bi

(1)

其中，ai和bi代表信道i上的節點參數。

利用最小二乘近似求得參數ai和bi[17]。該方法需要很小的計算開銷。根據樣本向量，通過最小化以下的式子得到式1中的兩個參數ai和bi。

(2)

因此，通過以下式子可以得到ai和bi的值：

(3)

其中，i為信道號；j為發送功率等級；N為不同的發送功率等級數量。

每個節點將不同的發送功率等級及父節點測到的相應的RSSI值應用于式3，這樣可以得到不同信道上的a和b兩個參數。每個節點根據使用的發送功率級別和不同信道上的a和b兩個參數，利用式1得到不同信道上的RSSI值，從而選擇RSSI值最大的信道，稱此信道為該節點的最佳信道。

根據以上方法，每個節點(除了匯聚節點)計算得到自己的最佳信道。選擇最佳信道進行通信可以提高數據包傳輸率，降低重傳次數。

3 R-MMAC協議

文中提出的基于預留的多信道MAC協議(R-MMAC)也使用了接收端發起的方法[18]。在這個過程中，當匯聚節點和中繼節點喚醒后，它們先向孩子節點發送喚醒信標。如果孩子節點有數據包要發送，則需要等到接收完喚醒信標之后。網絡中的節點根據喚醒調度和預留調度進行喚醒。喚醒調度和預留調度都包含調度的信道和時間。

喚醒調度用于接收潛在發送端的數據包。每個節點利用公共的偽隨機發生器確定未來的喚醒調度序列，其中節點的ID為種子。如果節點在喚醒調度時間中喚醒后，沒有通信要進行，則節點進入睡眠狀態。由于節點通過鄰居發現機制可以獲得鄰居節點的ID[19]，所以每個節點可以知道鄰居節點的喚醒調度。因此，發送節點根據父節點的喚醒調度時間，稍微提前喚醒，以便接收父節點的喚醒信標，從而傳輸數據包。

預留調度是發送端和接收端在傳輸周期性數據流的過程中制定的，用于發送以后的數據包。當傳輸周期性數據流的第一個數據包時，發送端和接收端預留周期性數據流的第二個數據包的傳輸。以此類推，發送端和接收端為未來數據包的傳輸制定預留調度。這樣發送端和接收端在預留調度的時間和信道上喚醒，可以及時地傳輸下一個數據包。

3.1 預留機制

預留機制包含三個階段：(1)預留建議階段；(2)預留決定階段；(3)添加預留階段。首先，所有節點根據自己的喚醒調度喚醒，匯聚節點和中繼節點在喚醒的信道上向孩子節點傳輸喚醒信標。如果孩子節點沒有數據包要傳輸，則進入睡眠狀態。由于節點知道父節點的喚醒調度，所以節點根據父節點的喚醒時間，提前喚醒。

首先，如果發送端有數據包要傳輸，則接收到喚醒信標之后在接收端所在的信道上傳輸數據包和對下一個數據包的建議A，A中包含建議的下一個數據包的傳輸時間和最佳信道，分別定義為ChA和tA。同時，發送端也將自己的預留調度列表L傳輸給接收端，以避免重疊預留。

其次，父節點接收到建議A后進入預留決定階段。父節點根據接收到的信息以及自己的預留調度列表決定最終預留的時間和信道，然后用信標B向發送端(孩子節點)傳輸預留決定D，D中包含決定進行傳輸的信道和下一次的傳輸時間(分別定義為ChD和tD)。

最后進入第三個階段，父節點和孩子節點將預留決定D(也就是ChD和tD)添加到自己的預留調度列表中。后面會仔細說明如何確定建議A和決定D。

算法1：預留機制。

1.Node state:(lea f,relay,sink)

2.Set of int children,parent

3.Message type data,suggestion A,reserved scheduling listL,wake up beacon,decision D

4.Ifi=sink ori=relay then

5.send wake up beacon to its children when it is awake

6.while true do

7.receive msg(j)

8.case msg.type of

9.data∧A∧Lj:send D tojand add D toLi

10.end while

11.Else

12.while true do

13.receive msg(j)

14.case msg.type of

15.wake_up beacon: send data,A andLito its parent

16.D:add D toLi

17.end while

18.End if

圖2顯示了由節點S向匯聚節點F傳輸數據的預留過程，其中考慮具有三個信道的網絡拓撲。

圖2 預留機制

3.2 預留中的沖突解決

如果一個節點至少有兩個孩子節點，那么在預留機制中有可能發生沖突。孩子節點同時向它們的公共父節點發送數據包，此時在父節點處發生沖突。這樣，父節點不再向孩子節點回復信標B，而是再次發送喚醒信標，其中包含退避的窗口大小，使得孩子節點重傳數據包。一段時間內，如果節點未收到回復信標B，則認為發送失敗，并等待來自父節點的回復。等待隨機退避一段時間之后，重傳數據包。

算法2:沖突解決算法。

//jreceives packets fromjn

//jn:the child of the current nodej:the parent node ofjn

1.If the node isjthen

2.jsends wake_up beacon including a back-off window size

3.Else if the node isjnthen

4.ifjnreceived D from j then

5.jncompletes the packet transmission and goes to sleep

6.else ifjnreceived wake up beacon including a back-off window size then

7.jnretransmits data packet after the random back-off time

8.end if

9.end if

10.end if

11.End if

圖3和圖4分別顯示了沖突拓撲和沖突的解決過程，節點j有兩個孩子節點，分別為j1和j2。假設節點j1、j2同時產生周期性數據流，且節點j和節點j1、j2都沒有預留，所以此時這些節點的預留調度列表L為空。

圖3 沖突拓撲

圖4 沖突解決

3.3 建議A和決定D

每個節點根據測到的不同信道上的RSSI值，向父節點建議最佳信道。當節點和父節點執行第一個數據包的傳輸時，它們會預留第二個數據包的傳輸，其中建議的信道為該節點選擇的最佳信道。根據周期性數據流中數據包的產生間隔，將產生第二個數據包的時刻預留為第二個數據包的傳輸時刻。這樣，可以盡可能早地傳輸第二個數據包。父節點接收到建議的信道和時間之后，同意建議的信道，將建議的信道作為決定中的信道。而對于預留的時間，父節點根據接收到的預留調度列表、自己的預留調度列表和建議的時間，選擇二者都處于喚醒狀態的最早時間作為預留的第二個數據包的傳輸時間。

3.4 重傳時間

已經有人研究了數據包接收率PRR和信干噪比SINR之間的關系。只要知道了接收端的SINR，根據已有的經驗PRR-SINR模型[20-21]就可以得到數據包接收率。

假設節點n1為發送節點，節點n2為接收節點，二者用信道x進行通信。同時利用信道x進行通信的其他k個發送接收節點對的集合為M={vi,vj,pmi}，vi為發送端，vj為接收端，pmi為發送端的發送功率。對于接收節點n2在信道x上的SINR值[22]可以計算如下：

(4)

然后根據已有的PRR-SINR模型，得到節點n1在信道x上向節點n2傳輸的PRR值。

根據得到的數據包接收率PRR決定預留的傳輸時間。實際上，數據包傳輸過程中總存在丟失現象，因此，設置一個數據包接收率閾值α，只要接收節點的數據包接收率PRR大于等于閾值α，則稱數據包接收成功。許多因素影響數據包接收率，如信道狀況、其他節點的干擾以及周圍的環境等等。當數據包丟失率較高時，通過重傳降低數據包丟失率。根據式5計算每個節點至少需要重傳的次數k：

(1-PRR)k+1≤(1-α)

(5)

其中，1-PRR表示數據包丟失率，得到至少需要的重傳次數k之后，即可計算需要預留的傳輸時間T：

(6)

4 性能評估

為了驗證性能，利用OMNET++5.3作為仿真工具，將所提的R-MMAC與典型的單信道MAC協議—X-MAC和多信道MAC協議—EM-MAC進行了性能比較。分別探索了數據包產生間隔和節點數目對端到端時延的影響。

在本次仿真中，將仿真區域設置為1 000 m*1 000 m，使用8個信道，每個信道的帶寬為250 kbps，節點的傳輸范圍為87 m。每次仿真運行50 s，并執行20次，計算其平均值。下面仔細說明數據包產生間隔和節點數目對端到端時延的影響。

4.1 數據包產生間隔對端到端時延的影響

在探究數據包產生間隔對時延的影響時，固定樹型拓撲的節點數為18，將數據包產生間隔分別設置為1 s、1.5 s、2 s、2.5 s、3 s、3.5 s和4 s。

圖5展示了隨著數據包產生間隔的變化，X-MAC、EM-MAC和R-MMAC協議從感知節點到匯聚節點的時延變化。

圖5 數據包產生間隔與端到端時延

可以看出隨著數據包產生間隔的增大，三種協議的端到端時延都呈現下降的趨勢，那是因為數據包產生間隔越大，需要傳輸的數據包個數較少，信道爭用現象不激烈。但是，明顯可以看出，當數據包產生間隔較小時，X-MAC產生的數據包時延較大。因為此時網絡中產生的數據包個數較多，單信道的信道爭用問題較為嚴重，并且沒有考慮相應的沖突解決方法。而對于EM-MAC協議和文中所提的R-MMAC協議，二者實現的時延明顯較小，因為它們都采用多信道通信方法，緩解了單個信道的資源爭用。然而，R-MMAC協議比EM-MAC協議的時延更低一點，因為R-MMAC選擇最佳的信道進行傳輸，利用較少的傳輸次數便可實現所需的數據包接收率，而EM-MAC協議只是避免了較差的傳輸信道，要想實現要求的數據包接收率，所需的時間相對較長一些。

4.2 節點數目對端到端時延的影響

探索節點數目產生的影響時，將數據包產生間隔設置為1 s，并將網絡中的節點數分別設置為3、6、9、12、15和18進行仿真。圖6展示了節點個數對X-MAC、EM-MAC和R-MMAC協議的端到端時延的影響。可以看出，隨著節點數目的增大，X-MAC的時延呈現上升趨勢，那是因為隨著節點數的增大，網絡中的負載增大，X-MAC協議采用的是單信道進行通信，并且沒有進一步考慮沖突的解決方法。而EM-MAC和R-MMAC協議，隨著節點數的增大，二者的傳輸時延變化不大，因為它們采用多信道通信，即使網絡負載增大，節點間的并行傳輸也有利于降低時延。但是，當網絡中的節點數為3時，R-MMAC協議的時延稍高于X-MAC和EM-MAC協議，因為R-MMAC需要選擇最佳信道，網絡負載較低時，選擇最佳信道的時間占用一定比例。然而隨著節點數的增大，當網絡中的負載較大時，R-MMAC的時延較低。

圖6 節點數與端到端時延

5 結束語

提出了一種基于預留的多信道MAC協議，稱為R-MMAC協議。R-MMAC協議是在多信道環境中實現的，并且利用了預留機制。在多信道條件下，每個節點根據接收信號強度指示RSSI值選擇自己的最佳信道進行預留。一方面，節點使用最佳信道傳輸數據，提高了網絡吞吐量。另一方面，利用預留機制降低了傳感器節點到匯聚節點的傳輸時延，因此也降低了未來數據包傳輸的沖突概率。另外，還提出了針對預留時發生沖突的解決算法。利用信干噪比SINR和數據包接收率PRR得到了預留的傳輸時間。在OMNET++5.3中將R-MMAC協議的性能與X-MAC和EM-MAC協議進行了比較。結果顯示R-MMAC協議實現了更低的端到端時延。未來隨著網絡密度的增大，節點之間的干擾問題會更加嚴重，在設計協議時，可以考慮加入相繼干擾消除技術，以提高協議的性能。