基于二叉樹沖突分解的物聯網隨機接入控制

杜銀霞，李紅睿，王春紅

(1.河北工程技術學院，河北 石家莊 050091;2.河北科技大學 ，河北 石家莊 050000)

1 引言

物聯網能夠借助信息傳感設備，將設備與Internet連接起來，按照統一制定的協議，進行通信和信息交換，實現不同設備之間的數據通信，而隨著物聯網設備的增加，支持通信網絡的需求也隨之增加，例如船舶飛機、跨省列車、衛星等，這些應用需求都需要物理層的接入技術，實現高頻次的數據傳輸，因此，對物聯網隨機接入進行研究，具有重要意義[1]。

國外物聯網隨機接入研究較早，提出多種隨機接入協議，定位發射端節點，在多個時隙上發送數據包，聯合多用戶連續干擾消除技術，使接收端對數據包進行譯碼，得到每個數據包信令中，包含的復本位置信息，再隨機選擇兩個時隙，通過發射端發送同一數據包的兩個復本，采用迭代干擾消除算法，使接收端解決數據包沖突問題，同時犧牲能量效率，對每個數據包發送不規則數目的復本，避免數據傳輸的吞吐量受限。國內物聯網隨機接入研究，同樣取得較大發展，設置共享的隨機接入信道，根據隨機多址協議，建立通信終端接入物聯網的場景，利用隨機競爭方式，使節點在公平條件下，以競爭的方式連接信道，融合協議和二叉樹沖突分解算法，避免連接節點與其它節點協商[2]。

在以上理論的基礎上，提出基于二叉樹沖突分解的物聯網隨機接入控制方法，在隨機接入協議中，利用二叉樹沖突分解算法，解決信道中信息分組的碰撞、擁塞沖突，確保節點間信息數據的高頻次傳輸。

2 基于二叉樹沖突分解的物聯網隨機接入控制方法設計

2.1 制定物聯網隨機接入路由協議

根據物聯網的網絡性能，制定物聯網隨機接入路由協議。使用多點傳播技術，優化鏈路狀態協議，對該協議進行擴展，使其滿足物聯網的網絡需求，得到物聯網隨機接入的OLSR路由協議[3]。通過OLSR協議，將物聯網劃分為3個覆蓋等級，具體如圖1所示。

圖1 物聯網接入協議的終端分布

根據終端所在信道環境，確定物聯網覆蓋等級，當最大耦合損耗超過165dB，等級為2，在145～165dB之間，等級為1，低于145dB，等級為0。在物聯網隨機接入前，采用單音跳頻的傳輸方式，結合符號組的概念，將5個符號和1個循環前綴，作為一個符號組，生成序列前導，并根據不同的覆蓋等級，對隨機接入信道參數進行配置[4]。具體跳頻前導方案如圖2所示。

圖2 單音跳頻前導方案

如上圖所示，灰色物理資源塊表示一個前導，通過全“1”序列，擴展生成前導序列包絡，通過子載波間隔和隨機接入信道帶寬，確定前導個數。采用跳頻的方式，定時估計基站端的到達時間，使前導僅包含時頻資源塊，從而保證不同覆蓋等級下，生成序列的前導長度，在隨機接入前，為節點基站累積足夠的能量[5]。在OLSR協議下，每個節點第一次收到消息時，對消息進行重傳，具體配置如表1所示。

表1 重發傳輸機制的信道配置

設置覆蓋等級2的最大重發次數為125，資源配置的前導周期最長，隨著等級的減小，降低重發次數并縮短前導周期，以此避免物聯網接入信道的資源消耗。接入信道配置完畢后，最小化OLSR協議的控制分組，使所有節點通過OLSR協議的控制分組，對物聯網拓撲信息進行收集，并將拓撲信息存儲在不同信息域中，讓節點得到整個物聯網的拓撲結構，使物聯網隨機接入時，可以直接轉發數據包的對應節點[6]。至此完成物聯網隨機接入路由協議的制定。

2.2 計算物聯網最優路由接入鏈路

優化最短路徑算法，選擇節點轉發的最優通信鏈路。將字節長度作為OLSR協議的分組長度，刷新一個OLSR分組傳遞，就增加一個新的分組序列號，使每個物聯網隨機接入接口，都匹配到單獨的分組序列號[7]。識別分組信息的有效時間域V為

(1)

式中，a、b分別表示時間域的高四位整數、低四位整數，ζ為比例因子[8]。當時間域V內，沒有識別出分組包含的信息數據，就將該分組進行丟棄，僅接受OLSR協議的有效分組。然后建立節點的重復集合，記錄接收分組的相關內容，確保無重復的檢查分組信息頭部，去除已處理的信息、以及分組長度小于分組頭部的信息，對剩余分組進行逐跳轉發。轉發過程中，首先檢測節點接入鏈路的方向性，周期廣播該節點的鄰居節點、以及鄰居節點鏈路狀態，選擇存在雙向鏈路的鄰居節點。設轉發節點為j，鄰居節點為i，則節點間鏈路信道的MAC層幀成功率ξ為

ξ=G(j)/N(i)

(2)

式中，G(j)為節點j發送MAC幀的總數量，N(i)為節點i成功接收的數量[9]。鏈路接口隊列的占用率η計算公式為

η=L(i)/C(i)

(3)

式中，L(i)為鄰居節點iMAC層接口隊列中，現有排隊的分組個數，C(i)為接口隊列排隊的最大可容納分組個數[10]。通過MAC層幀成功率和接口隊列占用率，更新轉發節點的鏈路狀態，其節點間鏈路狀態良好程度S(i，j)計算公式為

(4)

式中，Ki、Kj分別為節點i和節點j的空閑度，表示節點能夠接納后續負載的能力，α和β為預設指數[11]。綜合考慮兩跳鄰居集合的連通度、以及節點間鏈路狀態良好程度，計算一跳鄰居節點i的優先選擇因子Q，公式為

Q=d(τ)/S(i，j)

(5)

其中d(τ)為鄰居集合τ的連通度，即τ為轉發節點存在雙向鏈接的節點個數[12]。通過公式(5)，選擇節點間的最優鏈接路徑，使物聯網中每個節點都維持一個OLSR路由協議，使其能夠找到下一跳的轉發節點、目的節點地址，確定節點逐跳轉發序列的源節點和目的節點，構成一條物聯網隨機接入的最優路徑路由。至此完成物聯網最優路由接入鏈路的計算。

2.3 基于二叉樹沖突分解控制物聯網接入鏈路沖突

利用二叉樹沖突分解算法，控制接入鏈路信道的信息碰撞沖突。通過最優路由接入鏈路，發送包含節點信息的分組序列，利用二叉樹沖突分解算法，針對同一時隙發生沖突的信息分組，將其編為一組，同時讓與碰撞無關的信息分組暫時等待，當沖突解決完畢后，繼續發送信息數據。信息碰撞的分解過程如圖3所示，圓圈數字表示發生沖突的信息分組數目。

圖3 二叉樹沖突分解算法沖突分解過程

如圖3所示，當同一時隙上等待傳輸的信息分組為0，將該時隙看作空時隙，不進行分組傳輸，當信息分組為1，則立刻發送分組，當信息分組為2個或2個以上，則對碰撞的信息分組進行分解。計算信道沖突的平均分解次數E，公式為

(6)

其中p為傳輸時，一個時隙分配到信息分組的成功率，φ為信道碰撞的信息分組數，k為分配不成功的概率。經過E次分解后，將碰撞的信息分組劃分為多個子集，直至時隙空閑或時隙傳輸成功，退出沖突分解，確保物聯網接入鏈路中，信息分組的成功傳送，實現物聯網接入鏈路沖突的控制。至此完成基于二叉樹沖突分解算法，物聯網隨機接入控制方法的設計。

3 實驗論證分析

將此次設計方法記為實驗A組，兩種傳統物聯網隨機接入控制方法，分別為實驗B組和實驗C組，比較物聯網隨機接入后，節點傳輸信息數據的性能指標。共有 12 個 Lora 終端，采集溫度與濕度。網關通過路由器與業務服務器連接，業務服務器即 PC 一臺。Lora 網關將 Lora終端采集的信息上傳至業務服務器，最核心的部分為 Lora 網關。

圖4 隨機接入控制方法驗證平臺模型實物圖

3.1 實驗準備

采用MATLAB仿真軟件進行仿真，假設物聯網的網絡覆蓋范圍內，各節點均服從均勻分布，則實驗的設置參數如下表所示：

所有具有物聯網接入需求的終端，都在接入周期開始時刻發送接入請求，即周期內不存在新的接入請求。仿真環境考慮噪聲和信道衰落的影響，使用ITU-R M.1225信道模型，設置多普勒頻移為30kHz、萊斯因子為10dB，分別給出鏈路信道的小尺度衰落和大尺度衰落，并使其服從對數正態分布，標準差為3dB，均值為0dB，鏈路信道的帶寬為2.5Mbps，捕獲閾值為5dB，節點緩沖區可容納55個信息分組。

3.2 實驗結果

3.2.1 第一組實驗結果

所有仿真節點都配置兩塊無線網卡，使用Waypoint運動模型，該模型運動范圍為2000m×2000m，最大運動速度為30m/s，在緩沖區的停留時間為25s，網卡分別工作在兩個互不干擾的信道上。選取三種不同長度的數據包，符號數目分別為60、40、20，信噪比范圍分別為[6.5dB，10.8dB]、[10.8dB，20dB]、[20dB，∞]，數據包的比特數目都為1310，編號數據包分別為1、2、3，比較物聯網隨機接入后，不同歸一化負載下傳輸數據包的吞吐量，實驗結果如圖5所示。

表2 仿真參數初始設置

圖5 數據包1的吞吐量對比結果

由上圖可知，當數據包符號數目為60時，實驗A組的峰值吞吐量達到291kb/s，實驗B組和C組的峰值吞吐量分別為249kb/s、239kb/s，相比實驗B組和C組，A組數據吞吐量分別提高了42kb/s、52kb/s。第二種數據包的實驗對比結果如圖6所示。

圖6 數據包2的吞吐量對比結果

由上圖可知，當數據包符號數目為40時，實驗A組的峰值吞吐量達到271kb/s，實驗B組和C組的峰值吞吐量分別為233kb/s、191kb/s，相比實驗B組和C組，A組數據吞吐量分別提高了38kb/s、80kb/s。第三種數據包對比結果如圖7所示。

圖7 數據包3的吞吐量對比結果

由7圖可知，當數據包符號數目為20時，實驗A組的峰值吞吐量達到238kb/s，實驗B組和C組的峰值吞吐量分別為171kb/s、124kb/s，相比實驗B組和C組，A組數據吞吐量分別提高了67kb/s、114kb/s。

3.2.2 第二組實驗結果

選擇符號數目分別為40的數據包，設置接入鏈路的信道比為20dB，調節數據流的發送速率，設置仿真時間為500s，比較數據包端到端的延遲時間，實驗結果如表3所示。

表3 傳輸數據延遲時間對比結果

由表3可知，實驗A組傳輸數據的平均延遲時間為0.23s，實驗B組和實驗C組的平均延遲時間分別為0.37s、0.41s，相比實驗B組和C組，A組延遲時間分別縮短了0.14s、0.18s。

3.2.3 第三組實驗結果

前兩組實驗接入周期開始時刻的接入請求數為300，請求數較少，物聯網隨機接入的成功率為100%，增加接入請求數量，比較三組實驗的接入成功率，對比結果如表4所示。

表4 物聯網接入成功率對比結果(%)

由表4可知，實驗A組平均接入成功率為84.1%，實驗B組和實驗C組的平均成功率分別為79.6%、73.7%，相比實驗B組和實驗C組，A組成功率分別提高了4.5%、10.4%。綜上所述，此次設計方法提高了物聯網隨機接入的成功率，能夠處理大批量接入請求的節點設備，在此基礎上，提高了數據吞吐量，使節點通信時不需要多次重發信息數據，降低了物聯網接入的能量耗損，同時縮短了傳輸數據延遲時間，確保了物聯網接入后的通信效率。

4 結束語

此次設計方法充分發揮二叉樹沖突分解算法的優勢，提高了物聯網隨機接入的成功率和通信效率。但此次研究仍存在一定不足，在今后的研究中，會進一步細化分類終端，在接入請求調整時隙前，設計不同的接入參數，對前導資源進行劃分。