基于二叉樹(shù)沖突分解的物聯(lián)網(wǎng)隨機(jī)接入控制

杜銀霞，李紅睿，王春紅

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

1 引言

物聯(lián)網(wǎng)能夠借助信息傳感設(shè)備，將設(shè)備與Internet連接起來(lái)，按照統(tǒng)一制定的協(xié)議，進(jìn)行通信和信息交換，實(shí)現(xiàn)不同設(shè)備之間的數(shù)據(jù)通信，而隨著物聯(lián)網(wǎng)設(shè)備的增加，支持通信網(wǎng)絡(luò)的需求也隨之增加，例如船舶飛機(jī)、跨省列車、衛(wèi)星等，這些應(yīng)用需求都需要物理層的接入技術(shù)，實(shí)現(xiàn)高頻次的數(shù)據(jù)傳輸，因此，對(duì)物聯(lián)網(wǎng)隨機(jī)接入進(jìn)行研究，具有重要意義[1]。

國(guó)外物聯(lián)網(wǎng)隨機(jī)接入研究較早，提出多種隨機(jī)接入?yún)f(xié)議，定位發(fā)射端節(jié)點(diǎn)，在多個(gè)時(shí)隙上發(fā)送數(shù)據(jù)包，聯(lián)合多用戶連續(xù)干擾消除技術(shù)，使接收端對(duì)數(shù)據(jù)包進(jìn)行譯碼，得到每個(gè)數(shù)據(jù)包信令中，包含的復(fù)本位置信息，再隨機(jī)選擇兩個(gè)時(shí)隙，通過(guò)發(fā)射端發(fā)送同一數(shù)據(jù)包的兩個(gè)復(fù)本，采用迭代干擾消除算法，使接收端解決數(shù)據(jù)包沖突問(wèn)題，同時(shí)犧牲能量效率，對(duì)每個(gè)數(shù)據(jù)包發(fā)送不規(guī)則數(shù)目的復(fù)本，避免數(shù)據(jù)傳輸?shù)耐掏铝渴芟?。?guó)內(nèi)物聯(lián)網(wǎng)隨機(jī)接入研究，同樣取得較大發(fā)展，設(shè)置共享的隨機(jī)接入信道，根據(jù)隨機(jī)多址協(xié)議，建立通信終端接入物聯(lián)網(wǎng)的場(chǎng)景，利用隨機(jī)競(jìng)爭(zhēng)方式，使節(jié)點(diǎn)在公平條件下，以競(jìng)爭(zhēng)的方式連接信道，融合協(xié)議和二叉樹(shù)沖突分解算法，避免連接節(jié)點(diǎn)與其它節(jié)點(diǎn)協(xié)商[2]。

在以上理論的基礎(chǔ)上，提出基于二叉樹(shù)沖突分解的物聯(lián)網(wǎng)隨機(jī)接入控制方法，在隨機(jī)接入?yún)f(xié)議中，利用二叉樹(shù)沖突分解算法，解決信道中信息分組的碰撞、擁塞沖突，確保節(jié)點(diǎn)間信息數(shù)據(jù)的高頻次傳輸。

2 基于二叉樹(shù)沖突分解的物聯(lián)網(wǎng)隨機(jī)接入控制方法設(shè)計(jì)

2.1 制定物聯(lián)網(wǎng)隨機(jī)接入路由協(xié)議

根據(jù)物聯(lián)網(wǎng)的網(wǎng)絡(luò)性能，制定物聯(lián)網(wǎng)隨機(jī)接入路由協(xié)議。使用多點(diǎn)傳播技術(shù)，優(yōu)化鏈路狀態(tài)協(xié)議，對(duì)該協(xié)議進(jìn)行擴(kuò)展，使其滿足物聯(lián)網(wǎng)的網(wǎng)絡(luò)需求，得到物聯(lián)網(wǎng)隨機(jī)接入的OLSR路由協(xié)議[3]。通過(guò)OLSR協(xié)議，將物聯(lián)網(wǎng)劃分為3個(gè)覆蓋等級(jí)，具體如圖1所示。

圖1 物聯(lián)網(wǎng)接入?yún)f(xié)議的終端分布

根據(jù)終端所在信道環(huán)境，確定物聯(lián)網(wǎng)覆蓋等級(jí)，當(dāng)最大耦合損耗超過(guò)165dB，等級(jí)為2，在145～165dB之間，等級(jí)為1，低于145dB，等級(jí)為0。在物聯(lián)網(wǎng)隨機(jī)接入前，采用單音跳頻的傳輸方式，結(jié)合符號(hào)組的概念，將5個(gè)符號(hào)和1個(gè)循環(huán)前綴，作為一個(gè)符號(hào)組，生成序列前導(dǎo)，并根據(jù)不同的覆蓋等級(jí)，對(duì)隨機(jī)接入信道參數(shù)進(jìn)行配置[4]。具體跳頻前導(dǎo)方案如圖2所示。

圖2 單音跳頻前導(dǎo)方案

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

表1 重發(fā)傳輸機(jī)制的信道配置

設(shè)置覆蓋等級(jí)2的最大重發(fā)次數(shù)為125，資源配置的前導(dǎo)周期最長(zhǎng)，隨著等級(jí)的減小，降低重發(fā)次數(shù)并縮短前導(dǎo)周期，以此避免物聯(lián)網(wǎng)接入信道的資源消耗。接入信道配置完畢后，最小化OLSR協(xié)議的控制分組，使所有節(jié)點(diǎn)通過(guò)OLSR協(xié)議的控制分組，對(duì)物聯(lián)網(wǎng)拓?fù)湫畔⑦M(jìn)行收集，并將拓?fù)湫畔⒋鎯?chǔ)在不同信息域中，讓節(jié)點(diǎn)得到整個(gè)物聯(lián)網(wǎng)的拓?fù)浣Y(jié)構(gòu)，使物聯(lián)網(wǎng)隨機(jī)接入時(shí)，可以直接轉(zhuǎn)發(fā)數(shù)據(jù)包的對(duì)應(yīng)節(jié)點(diǎn)[6]。至此完成物聯(lián)網(wǎng)隨機(jī)接入路由協(xié)議的制定。

2.2 計(jì)算物聯(lián)網(wǎng)最優(yōu)路由接入鏈路

優(yōu)化最短路徑算法，選擇節(jié)點(diǎn)轉(zhuǎn)發(fā)的最優(yōu)通信鏈路。將字節(jié)長(zhǎng)度作為OLSR協(xié)議的分組長(zhǎng)度，刷新一個(gè)OLSR分組傳遞，就增加一個(gè)新的分組序列號(hào)，使每個(gè)物聯(lián)網(wǎng)隨機(jī)接入接口，都匹配到單獨(dú)的分組序列號(hào)[7]。識(shí)別分組信息的有效時(shí)間域V為

(1)

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

ξ=G(j)/N(i)

(2)

式中，G(j)為節(jié)點(diǎn)j發(fā)送MAC幀的總數(shù)量，N(i)為節(jié)點(diǎn)i成功接收的數(shù)量[9]。鏈路接口隊(duì)列的占用率η計(jì)算公式為

η=L(i)/C(i)

(3)

式中，L(i)為鄰居節(jié)點(diǎn)iMAC層接口隊(duì)列中，現(xiàn)有排隊(duì)的分組個(gè)數(shù)，C(i)為接口隊(duì)列排隊(duì)的最大可容納分組個(gè)數(shù)[10]。通過(guò)MAC層幀成功率和接口隊(duì)列占用率，更新轉(zhuǎn)發(fā)節(jié)點(diǎn)的鏈路狀態(tài)，其節(jié)點(diǎn)間鏈路狀態(tài)良好程度S(i，j)計(jì)算公式為

(4)

式中，Ki、Kj分別為節(jié)點(diǎn)i和節(jié)點(diǎn)j的空閑度，表示節(jié)點(diǎn)能夠接納后續(xù)負(fù)載的能力，α和β為預(yù)設(shè)指數(shù)[11]。綜合考慮兩跳鄰居集合的連通度、以及節(jié)點(diǎn)間鏈路狀態(tài)良好程度，計(jì)算一跳鄰居節(jié)點(diǎn)i的優(yōu)先選擇因子Q，公式為

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

(5)

其中d(τ)為鄰居集合τ的連通度，即τ為轉(zhuǎn)發(fā)節(jié)點(diǎn)存在雙向鏈接的節(jié)點(diǎn)個(gè)數(shù)[12]。通過(guò)公式(5)，選擇節(jié)點(diǎn)間的最優(yōu)鏈接路徑，使物聯(lián)網(wǎng)中每個(gè)節(jié)點(diǎn)都維持一個(gè)OLSR路由協(xié)議，使其能夠找到下一跳的轉(zhuǎn)發(fā)節(jié)點(diǎn)、目的節(jié)點(diǎn)地址，確定節(jié)點(diǎn)逐跳轉(zhuǎn)發(fā)序列的源節(jié)點(diǎn)和目的節(jié)點(diǎn)，構(gòu)成一條物聯(lián)網(wǎng)隨機(jī)接入的最優(yōu)路徑路由。至此完成物聯(lián)網(wǎng)最優(yōu)路由接入鏈路的計(jì)算。

2.3 基于二叉樹(shù)沖突分解控制物聯(lián)網(wǎng)接入鏈路沖突

利用二叉樹(shù)沖突分解算法，控制接入鏈路信道的信息碰撞沖突。通過(guò)最優(yōu)路由接入鏈路，發(fā)送包含節(jié)點(diǎn)信息的分組序列，利用二叉樹(shù)沖突分解算法，針對(duì)同一時(shí)隙發(fā)生沖突的信息分組，將其編為一組，同時(shí)讓與碰撞無(wú)關(guān)的信息分組暫時(shí)等待，當(dāng)沖突解決完畢后，繼續(xù)發(fā)送信息數(shù)據(jù)。信息碰撞的分解過(guò)程如圖3所示，圓圈數(shù)字表示發(fā)生沖突的信息分組數(shù)目。

圖3 二叉樹(shù)沖突分解算法沖突分解過(guò)程

如圖3所示，當(dāng)同一時(shí)隙上等待傳輸?shù)男畔⒎纸M為0，將該時(shí)隙看作空時(shí)隙，不進(jìn)行分組傳輸，當(dāng)信息分組為1，則立刻發(fā)送分組，當(dāng)信息分組為2個(gè)或2個(gè)以上，則對(duì)碰撞的信息分組進(jìn)行分解。計(jì)算信道沖突的平均分解次數(shù)E，公式為

(6)

其中p為傳輸時(shí)，一個(gè)時(shí)隙分配到信息分組的成功率，φ為信道碰撞的信息分組數(shù)，k為分配不成功的概率。經(jīng)過(guò)E次分解后，將碰撞的信息分組劃分為多個(gè)子集，直至?xí)r隙空閑或時(shí)隙傳輸成功，退出沖突分解，確保物聯(lián)網(wǎng)接入鏈路中，信息分組的成功傳送，實(shí)現(xiàn)物聯(lián)網(wǎng)接入鏈路沖突的控制。至此完成基于二叉樹(shù)沖突分解算法，物聯(lián)網(wǎng)隨機(jī)接入控制方法的設(shè)計(jì)。

3 實(shí)驗(yàn)論證分析

將此次設(shè)計(jì)方法記為實(shí)驗(yàn)A組，兩種傳統(tǒng)物聯(lián)網(wǎng)隨機(jī)接入控制方法，分別為實(shí)驗(yàn)B組和實(shí)驗(yàn)C組，比較物聯(lián)網(wǎng)隨機(jī)接入后，節(jié)點(diǎn)傳輸信息數(shù)據(jù)的性能指標(biāo)。共有 12 個(gè) Lora 終端，采集溫度與濕度。網(wǎng)關(guān)通過(guò)路由器與業(yè)務(wù)服務(wù)器連接，業(yè)務(wù)服務(wù)器即 PC 一臺(tái)。Lora 網(wǎng)關(guān)將 Lora終端采集的信息上傳至業(yè)務(wù)服務(wù)器，最核心的部分為 Lora 網(wǎng)關(guān)。

圖4 隨機(jī)接入控制方法驗(yàn)證平臺(tái)模型實(shí)物圖

3.1 實(shí)驗(yàn)準(zhǔn)備

采用MATLAB仿真軟件進(jìn)行仿真，假設(shè)物聯(lián)網(wǎng)的網(wǎng)絡(luò)覆蓋范圍內(nèi)，各節(jié)點(diǎn)均服從均勻分布，則實(shí)驗(yàn)的設(shè)置參數(shù)如下表所示：

所有具有物聯(lián)網(wǎng)接入需求的終端，都在接入周期開(kāi)始時(shí)刻發(fā)送接入請(qǐng)求，即周期內(nèi)不存在新的接入請(qǐng)求。仿真環(huán)境考慮噪聲和信道衰落的影響，使用ITU-R M.1225信道模型，設(shè)置多普勒頻移為30kHz、萊斯因子為10dB，分別給出鏈路信道的小尺度衰落和大尺度衰落，并使其服從對(duì)數(shù)正態(tài)分布，標(biāo)準(zhǔn)差為3dB，均值為0dB，鏈路信道的帶寬為2.5Mbps，捕獲閾值為5dB，節(jié)點(diǎn)緩沖區(qū)可容納55個(gè)信息分組。

3.2 實(shí)驗(yàn)結(jié)果

3.2.1 第一組實(shí)驗(yàn)結(jié)果

所有仿真節(jié)點(diǎn)都配置兩塊無(wú)線網(wǎng)卡，使用Waypoint運(yùn)動(dòng)模型，該模型運(yùn)動(dòng)范圍為2000m×2000m，最大運(yùn)動(dòng)速度為30m/s，在緩沖區(qū)的停留時(shí)間為25s，網(wǎng)卡分別工作在兩個(gè)互不干擾的信道上。選取三種不同長(zhǎng)度的數(shù)據(jù)包，符號(hào)數(shù)目分別為60、40、20，信噪比范圍分別為[6.5dB，10.8dB]、[10.8dB，20dB]、[20dB，∞]，數(shù)據(jù)包的比特?cái)?shù)目都為1310，編號(hào)數(shù)據(jù)包分別為1、2、3，比較物聯(lián)網(wǎng)隨機(jī)接入后，不同歸一化負(fù)載下傳輸數(shù)據(jù)包的吞吐量，實(shí)驗(yàn)結(jié)果如圖5所示。

表2 仿真參數(shù)初始設(shè)置

圖5 數(shù)據(jù)包1的吞吐量對(duì)比結(jié)果

由上圖可知，當(dāng)數(shù)據(jù)包符號(hào)數(shù)目為60時(shí)，實(shí)驗(yàn)A組的峰值吞吐量達(dá)到291kb/s，實(shí)驗(yàn)B組和C組的峰值吞吐量分別為249kb/s、239kb/s，相比實(shí)驗(yàn)B組和C組，A組數(shù)據(jù)吞吐量分別提高了42kb/s、52kb/s。第二種數(shù)據(jù)包的實(shí)驗(yàn)對(duì)比結(jié)果如圖6所示。

圖6 數(shù)據(jù)包2的吞吐量對(duì)比結(jié)果

由上圖可知，當(dāng)數(shù)據(jù)包符號(hào)數(shù)目為40時(shí)，實(shí)驗(yàn)A組的峰值吞吐量達(dá)到271kb/s，實(shí)驗(yàn)B組和C組的峰值吞吐量分別為233kb/s、191kb/s，相比實(shí)驗(yàn)B組和C組，A組數(shù)據(jù)吞吐量分別提高了38kb/s、80kb/s。第三種數(shù)據(jù)包對(duì)比結(jié)果如圖7所示。

圖7 數(shù)據(jù)包3的吞吐量對(duì)比結(jié)果

由7圖可知，當(dāng)數(shù)據(jù)包符號(hào)數(shù)目為20時(shí)，實(shí)驗(yàn)A組的峰值吞吐量達(dá)到238kb/s，實(shí)驗(yàn)B組和C組的峰值吞吐量分別為171kb/s、124kb/s，相比實(shí)驗(yàn)B組和C組，A組數(shù)據(jù)吞吐量分別提高了67kb/s、114kb/s。

3.2.2 第二組實(shí)驗(yàn)結(jié)果

選擇符號(hào)數(shù)目分別為40的數(shù)據(jù)包，設(shè)置接入鏈路的信道比為20dB，調(diào)節(jié)數(shù)據(jù)流的發(fā)送速率，設(shè)置仿真時(shí)間為500s，比較數(shù)據(jù)包端到端的延遲時(shí)間，實(shí)驗(yàn)結(jié)果如表3所示。

表3 傳輸數(shù)據(jù)延遲時(shí)間對(duì)比結(jié)果

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

3.2.3 第三組實(shí)驗(yàn)結(jié)果

前兩組實(shí)驗(yàn)接入周期開(kāi)始時(shí)刻的接入請(qǐng)求數(shù)為300，請(qǐng)求數(shù)較少，物聯(lián)網(wǎng)隨機(jī)接入的成功率為100%，增加接入請(qǐng)求數(shù)量，比較三組實(shí)驗(yàn)的接入成功率，對(duì)比結(jié)果如表4所示。

表4 物聯(lián)網(wǎng)接入成功率對(duì)比結(jié)果(%)

由表4可知，實(shí)驗(yàn)A組平均接入成功率為84.1%，實(shí)驗(yàn)B組和實(shí)驗(yàn)C組的平均成功率分別為79.6%、73.7%，相比實(shí)驗(yàn)B組和實(shí)驗(yàn)C組，A組成功率分別提高了4.5%、10.4%。綜上所述，此次設(shè)計(jì)方法提高了物聯(lián)網(wǎng)隨機(jī)接入的成功率，能夠處理大批量接入請(qǐng)求的節(jié)點(diǎn)設(shè)備，在此基礎(chǔ)上，提高了數(shù)據(jù)吞吐量，使節(jié)點(diǎn)通信時(shí)不需要多次重發(fā)信息數(shù)據(jù)，降低了物聯(lián)網(wǎng)接入的能量耗損，同時(shí)縮短了傳輸數(shù)據(jù)延遲時(shí)間，確保了物聯(lián)網(wǎng)接入后的通信效率。

4 結(jié)束語(yǔ)

此次設(shè)計(jì)方法充分發(fā)揮二叉樹(shù)沖突分解算法的優(yōu)勢(shì)，提高了物聯(lián)網(wǎng)隨機(jī)接入的成功率和通信效率。但此次研究仍存在一定不足，在今后的研究中，會(huì)進(jìn)一步細(xì)化分類終端，在接入請(qǐng)求調(diào)整時(shí)隙前，設(shè)計(jì)不同的接入?yún)?shù)，對(duì)前導(dǎo)資源進(jìn)行劃分。