面向M2M通信的網(wǎng)絡(luò)分層與窗口控制接入策略

李姣軍,楊 川,楊 凡,喻 濤,杜源昌,陳征驥

(1.重慶理工大學(xué) 電氣與電子工程學(xué)院, 重慶 400054;2.重慶川儀自動(dòng)化股份有限公司, 重慶 400700)

0 引言

隨著無(wú)線通信技術(shù)的發(fā)展,5G通信技術(shù)更加成熟,為機(jī)器與機(jī)器(machine to machine,M2M)通信提供了很好的技術(shù)支持。M2M通信同人與人(human to human,H2H)之間的通信相似,機(jī)器類型通信(machine type communication,MTC)設(shè)備在實(shí)現(xiàn)通信功能之前,需要完成隨機(jī)接入過(guò)程與基站建立連接。但是MTC設(shè)備的部署密集程度遠(yuǎn)超一般通信設(shè)備的部署密集程度[1],導(dǎo)致海量設(shè)備在接入時(shí)因MTC設(shè)備間的通信干擾更容易引起接入沖突。另一方面,由于MTC設(shè)備數(shù)量多、接入資源緊張,因此當(dāng)大量MTC設(shè)備同時(shí)向基站發(fā)起接入時(shí),必然會(huì)使得部分MTC設(shè)備因選中相同的接入資源而導(dǎo)致接入沖突,嚴(yán)重時(shí)造成網(wǎng)絡(luò)擁塞,使所有MTC設(shè)備接入失敗[2]。

為緩解大規(guī)模機(jī)器類通信中接入沖突、網(wǎng)絡(luò)擁塞的問(wèn)題,國(guó)內(nèi)外提出了多種隨機(jī)接入控制策略,主要包括接入控制限制(access control barring,ACB)、退避指示(backoff indictor,BI)、動(dòng)態(tài)ACB等方法[3]。ACB控制方案本質(zhì)是給MTC設(shè)備和基站分配一個(gè)ACB因子,若MTC設(shè)備的ACB因子小于基站的ACB因子,則允許該設(shè)備發(fā)起接入,反之則不允許發(fā)起接入,從而降低每個(gè)接入機(jī)會(huì)(random access opportunities,RO)上發(fā)起接入的設(shè)備數(shù)量。動(dòng)態(tài)ACB方案根據(jù)預(yù)測(cè)的接入設(shè)備數(shù)量來(lái)調(diào)整ACB因子大小。文獻(xiàn)[4-6]中通過(guò)調(diào)整ACB參數(shù)控制每個(gè)隨機(jī)接入時(shí)隙中的發(fā)起接入設(shè)備數(shù)量,但該方案只適用于設(shè)備數(shù)量較少的情況。Zhou等[7]通過(guò)將ACB機(jī)制與資源分配相結(jié)合來(lái)提高小區(qū)內(nèi)接入吞吐量,解決了隨機(jī)接入擁塞的問(wèn)題,但接入時(shí)延較高。文獻(xiàn)[8-9]提出的動(dòng)態(tài)ACB是根據(jù)每個(gè)接入時(shí)隙活躍的設(shè)備數(shù)量來(lái)估計(jì)ACB因子,但現(xiàn)有估計(jì)算法比較簡(jiǎn)單,不能使接入吞吐量性能達(dá)到最佳。BI算法是在設(shè)備發(fā)起接入請(qǐng)求后沒(méi)有收到基站的接入響應(yīng)(random access response,RAR)時(shí),基站會(huì)給設(shè)備分配一個(gè)BI值,使設(shè)備在等待一段時(shí)間后重新發(fā)起接入以緩解接入沖突。Xu等[10]中提出的退避方案,通過(guò)給每個(gè)設(shè)備隨機(jī)分配一個(gè)退避時(shí)間從而達(dá)到緩解沖突的目的,但是退避時(shí)間會(huì)導(dǎo)致接入時(shí)延較高。孫君等[11]在ACB控制的基礎(chǔ)上提出一種基于退避預(yù)測(cè)的動(dòng)態(tài)ACB控制方案來(lái)降低接入沖突,但該方案只適用于環(huán)境簡(jiǎn)單、設(shè)備數(shù)量較少的場(chǎng)景。綜上所述,上述大部分接入控制方案只適用接入設(shè)備數(shù)量較少的場(chǎng)景,或者接入所需時(shí)延較高,無(wú)法滿足MTC設(shè)備大規(guī)模接入的需求。

網(wǎng)絡(luò)分層是目前解決MTC設(shè)備部署密集而引起接入沖突的主要手段。網(wǎng)絡(luò)分層通過(guò)將小區(qū)內(nèi)的MTC設(shè)備分配到不同分組內(nèi),簡(jiǎn)化小區(qū)接入網(wǎng)的網(wǎng)絡(luò)結(jié)構(gòu),從而降低小區(qū)內(nèi)的設(shè)備接入沖突數(shù)量。劉冬雪等[12]提出一種分層接入的方法來(lái)提高接入資源的利用率和接入成功率,但未考慮MTC設(shè)備同時(shí)出現(xiàn)在多個(gè)分組內(nèi)的情況,導(dǎo)致MTC設(shè)備找不到接入對(duì)象,增加了算法的復(fù)雜度。Jang等[13]提出根據(jù)業(yè)務(wù)到達(dá)率對(duì)小區(qū)設(shè)備分組和按照每個(gè)分組內(nèi)請(qǐng)求接入的數(shù)量分配前導(dǎo)碼,但該方法接入時(shí)延較高。文獻(xiàn)[14-15]提出k鄰近算法對(duì)不同MTC設(shè)備按照聚類進(jìn)行分層,但該算法針對(duì)小區(qū)邊緣MTC設(shè)備,且要求分層間的資源兩兩正交,不適合應(yīng)用于資源緊張的接入網(wǎng)。邵羽豐等[16]提出了一種基于網(wǎng)絡(luò)分層的ACB控制方案提高了接入成功率,但該方案由于ACB因子的隨機(jī)性,會(huì)導(dǎo)致接入時(shí)延較高。李軍等[17]提出了采用滑動(dòng)窗口控制的方法來(lái)控制每個(gè)接入時(shí)隙發(fā)起接入的設(shè)備數(shù)量,提高了接入成功率,降低了平均接入時(shí)延,但未考慮接入資源不足的問(wèn)題。以上方案均只考慮了降低每個(gè)接入時(shí)隙的設(shè)備數(shù)量和接入沖突,沒(méi)有考慮接入資源與接入時(shí)延帶來(lái)的影響,很難支撐大規(guī)模機(jī)器類通信隨機(jī)接入的需求。

為了解決大規(guī)模M2M通信網(wǎng)絡(luò)擁塞、接入時(shí)延高的問(wèn)題,提出一種網(wǎng)絡(luò)分層技術(shù)結(jié)合窗口控制技術(shù)的算法。首先建立骨干接入網(wǎng)絡(luò)模型,提出接入網(wǎng)絡(luò)分層優(yōu)化算法,優(yōu)化骨干接入節(jié)點(diǎn)集合,集合中的接入節(jié)點(diǎn)代表了簇頭設(shè)備,實(shí)現(xiàn)網(wǎng)絡(luò)分層。通過(guò)建立骨干接入網(wǎng)絡(luò)模型和接入子網(wǎng)模型,提出了窗口控制和前導(dǎo)碼復(fù)用策略,實(shí)現(xiàn)對(duì)MTC設(shè)備的接入控制。該方法可以使每個(gè)接入時(shí)隙內(nèi)成功接入的設(shè)備數(shù)量最大化,降低設(shè)備接入沖突和接入時(shí)延,從而提高小區(qū)的接入成功率。

1 系統(tǒng)模型

系統(tǒng)模型如圖1所示,通信基站位于小區(qū)中心,負(fù)責(zé)接收小區(qū)內(nèi)所有MTC設(shè)備的隨機(jī)接入請(qǐng)求,并將MTC設(shè)備接入網(wǎng)絡(luò)。小區(qū)中有M個(gè)可用前導(dǎo)碼(preamble,PA),N個(gè)MTC設(shè)備隨機(jī)分布在小區(qū)內(nèi),其中MTC設(shè)備主要分為水電抄表、智能家居設(shè)備、遠(yuǎn)程監(jiān)測(cè)設(shè)備等靜態(tài)分布設(shè)備。

圖1 系統(tǒng)模型示意圖

由于MTC設(shè)備通過(guò)競(jìng)爭(zhēng)型隨機(jī)接入方式向基站發(fā)起接入請(qǐng)求,且設(shè)備部署量龐大,當(dāng)大量MTC設(shè)備突然涌入網(wǎng)絡(luò)并向基站發(fā)起隨機(jī)接入請(qǐng)求時(shí),必然會(huì)因?yàn)橛邢薜慕尤胭Y源競(jìng)爭(zhēng)而引起接入沖突,甚至導(dǎo)致小區(qū)網(wǎng)絡(luò)擁塞。針對(duì)MTC設(shè)備接入沖突問(wèn)題,用無(wú)向圖G=(V,E)來(lái)表示MTC設(shè)備間的通信關(guān)系。其中V表示節(jié)點(diǎn)集合,E為邊集合,節(jié)點(diǎn)和邊分別代表了MTC設(shè)備和MTC設(shè)備之間的通信鏈路,用鄰接矩陣A表示節(jié)點(diǎn)之間的通信關(guān)系。

2 網(wǎng)絡(luò)分層算法

在隨機(jī)接入過(guò)程的第一步中,MTC設(shè)備向基站發(fā)送PA。MTC設(shè)備可選擇的PA數(shù)量有限[18],最多不超過(guò)64個(gè)。多個(gè)MTC設(shè)備在同一接入時(shí)隙向基站發(fā)起接入引起前導(dǎo)碼碰撞,這種情況視為隨機(jī)接入發(fā)起失敗,因此為提高小區(qū)內(nèi)MTC設(shè)備的接入成功率,使用網(wǎng)絡(luò)分層來(lái)減少在同一接入時(shí)隙內(nèi)選擇相同PA的MTC設(shè)備數(shù)量。

通過(guò)分層接入的思想使MTC設(shè)備分組接入,建立骨干接入網(wǎng)絡(luò)模型,解決接入資源不足的問(wèn)題。首先,對(duì)小區(qū)MTC設(shè)備分組時(shí),需要根據(jù)MTC的通信范圍和位置,作出小區(qū)接入網(wǎng)的網(wǎng)絡(luò)拓?fù)鋱D;在得到網(wǎng)絡(luò)拓?fù)鋱D后,利用定時(shí)提前量(timing advance,TA)分組并建立骨干接入網(wǎng)絡(luò),考慮到接入資源緊張,提出最小骨干接入節(jié)點(diǎn)集算法,進(jìn)一步減少骨干接入網(wǎng)絡(luò)中的接入節(jié)點(diǎn)數(shù)量,優(yōu)化骨干接入網(wǎng)絡(luò);為了保證MTC設(shè)備之間、MTC設(shè)備與基站的通信質(zhì)量,在建立骨干接入網(wǎng)絡(luò)模型時(shí)需要考慮節(jié)點(diǎn)之間的距離,需要以最少的接入節(jié)點(diǎn)數(shù)量覆蓋整個(gè)網(wǎng)絡(luò),同時(shí)每個(gè)接入節(jié)點(diǎn)所管理的節(jié)點(diǎn)數(shù)不能相差太大,并減少節(jié)點(diǎn)被多個(gè)接入節(jié)點(diǎn)管理的次數(shù),否則會(huì)造成接入資源浪費(fèi)[19]。

2.1 初始分層-建立骨干接入網(wǎng)絡(luò)模型

根據(jù)MTC設(shè)備之間的通信關(guān)系得到小區(qū)通信網(wǎng)絡(luò)的無(wú)向拓?fù)鋱DG,如圖2所示,小區(qū)中的每個(gè)MTC設(shè)備對(duì)應(yīng)圖2中的節(jié)點(diǎn)V,任意2個(gè)可以互相通信的節(jié)點(diǎn)相連構(gòu)成邊E。

圖2 小區(qū)的無(wú)向接入網(wǎng)絡(luò)拓?fù)鋱D

網(wǎng)絡(luò)拓?fù)鋱D中邊的長(zhǎng)度為節(jié)點(diǎn)之間的距離,設(shè)節(jié)點(diǎn)Vi和Vj的坐標(biāo)分別為(xi,yi)、(xj,yj),則節(jié)點(diǎn)Vi與節(jié)點(diǎn)Vj之間的歐式距離為

(1)

為了保證節(jié)點(diǎn)之間的通信質(zhì)量,節(jié)點(diǎn)間的物理距離應(yīng)該小于通信距離。d是判斷每個(gè)節(jié)點(diǎn)是否可以通信的閾值,則每個(gè)節(jié)點(diǎn)之間的通信關(guān)系可以表示成:

(2)

其中Oij=1表示節(jié)點(diǎn)Vi與節(jié)點(diǎn)Vj可以通信。d根據(jù)TA與物理距離之間的關(guān)系計(jì)算,計(jì)算式為

d=TA×DTA,TA=0,1,2,…

(3)

DTA=16×c×Ts/2

(4)

Ts=1/(SCS×NFFT)

(5)

其中:c是光速;SCS表示子載波間隔;NFFT表示FFT運(yùn)算點(diǎn)數(shù)。由式(2)可以得到整個(gè)小區(qū)MTC設(shè)備接入網(wǎng)的鄰接矩陣為

(6)

由式(6)中的鄰接矩陣可作出小區(qū)接入網(wǎng)的網(wǎng)絡(luò)拓?fù)鋱D,然后在網(wǎng)絡(luò)拓?fù)鋱D的基礎(chǔ)上求解骨干接入節(jié)點(diǎn)集,骨干接入節(jié)點(diǎn)集數(shù)學(xué)表示方法為:

(7)

其中:V為節(jié)點(diǎn)集合;S為骨干節(jié)點(diǎn)集合;N(u)為節(jié)點(diǎn)u的一跳鄰接節(jié)點(diǎn)集合。

當(dāng)節(jié)點(diǎn)在網(wǎng)絡(luò)拓?fù)鋱D中都處于初始狀態(tài)時(shí),即MTC設(shè)備處于開(kāi)機(jī)未接入的狀態(tài),算法隨機(jī)選擇開(kāi)始節(jié)點(diǎn),它們向自己的相鄰節(jié)點(diǎn)發(fā)送握手消息,并統(tǒng)計(jì)自己接收的握手消息中的分值信息。然后,在由起始節(jié)點(diǎn)和它的相鄰節(jié)點(diǎn)組成的網(wǎng)絡(luò)中,將分值最大的節(jié)點(diǎn)設(shè)置為初始節(jié)點(diǎn)并添加到初始解S中,分值計(jì)算式為:

(8)

其中:score(u)為節(jié)點(diǎn)u的分值;S為骨干節(jié)點(diǎn)的集合;C1是將u加入S后由未被覆蓋變?yōu)楸桓采w的節(jié)點(diǎn)的集合,C2是通過(guò)將u從S中移除由被覆蓋變?yōu)槲幢桓采w的節(jié)點(diǎn)的集合;Nfreq表示每個(gè)節(jié)點(diǎn)的頻率值。每個(gè)節(jié)點(diǎn)的初始頻率值被設(shè)置為1,通過(guò)不斷局部搜索迭代更新Nfreq,每一次沒(méi)有被覆蓋的節(jié)點(diǎn)的Nfreq增加1,節(jié)點(diǎn)的Nfreq越大,被選為骨干節(jié)點(diǎn)的概率就越大。小區(qū)初始骨干接入網(wǎng)建立具體步驟如下:

步驟1隨機(jī)選擇節(jié)點(diǎn)v向其相鄰節(jié)點(diǎn)發(fā)送握手消息,統(tǒng)計(jì)分值信息并建立小區(qū)的網(wǎng)絡(luò)拓?fù)鋱D;

步驟2對(duì)節(jié)點(diǎn)v及其相鄰節(jié)點(diǎn)的分值進(jìn)行比較,選擇分值最大的節(jié)點(diǎn)u加入候選解S,作為骨干接入節(jié)點(diǎn);

步驟3將節(jié)點(diǎn)u及其單跳鄰接節(jié)點(diǎn)的編號(hào)從節(jié)點(diǎn)集合中去除;

步驟4在剩余節(jié)點(diǎn)中重復(fù)步驟2和3,直到所有節(jié)點(diǎn)都被覆蓋;

步驟5選擇出的骨干接入節(jié)點(diǎn)構(gòu)成的網(wǎng)絡(luò)就是初始骨干網(wǎng)絡(luò)。

通過(guò)建立小區(qū)初始骨干接入網(wǎng)絡(luò)對(duì)小區(qū)的接入網(wǎng)絡(luò)實(shí)現(xiàn)簡(jiǎn)化。然而,初始骨干網(wǎng)絡(luò)中的接入節(jié)點(diǎn)數(shù)目較多,一些節(jié)點(diǎn)存在被多個(gè)接入節(jié)點(diǎn)支配的情況,還需要對(duì)網(wǎng)絡(luò)進(jìn)一步優(yōu)化,初始骨干接入網(wǎng)絡(luò)模型如圖3所示。

圖3 初始骨干接入網(wǎng)絡(luò)模型示意圖

初始骨干接入網(wǎng)絡(luò)模型中的節(jié)點(diǎn)V和重疊節(jié)點(diǎn)組成第二層網(wǎng)絡(luò)-接入子網(wǎng)。其中,節(jié)點(diǎn)V可以直接向其所屬的接入節(jié)點(diǎn)發(fā)起接入,而重疊節(jié)點(diǎn)可以向多個(gè)接入節(jié)點(diǎn)發(fā)起接入,會(huì)對(duì)節(jié)點(diǎn)V造成接入干擾。

2.2 分層優(yōu)化-最小骨干接入節(jié)點(diǎn)集

初始骨干接入網(wǎng)絡(luò)中的骨干接入節(jié)點(diǎn)個(gè)數(shù)較多,為了使普通節(jié)點(diǎn)有足夠的接入資源,需要簡(jiǎn)化初始骨干接入網(wǎng)絡(luò),通過(guò)不斷優(yōu)化找出最小骨干接入節(jié)點(diǎn)集,即以最少的骨干接入節(jié)點(diǎn)覆蓋整個(gè)網(wǎng)絡(luò)。

根據(jù)最小骨干接入節(jié)點(diǎn)集的定義及滿足條件,建立最小骨干接入節(jié)點(diǎn)集的數(shù)學(xué)模型。最小骨干接入節(jié)點(diǎn)集的數(shù)學(xué)模型表示為

(9)

(10)

11)

(12)

其中:CBN表示求解最小骨干接入節(jié)點(diǎn)集合;Cm表示節(jié)點(diǎn)之間的通信關(guān)系,在降低骨干接入節(jié)點(diǎn)支配區(qū)域的重疊范圍時(shí),其約束條件為節(jié)點(diǎn)是接入節(jié)點(diǎn)或鄰接節(jié)點(diǎn);n表示節(jié)點(diǎn)數(shù)量。

為了防止局部搜索出來(lái)的解是局部最優(yōu)解,引入了環(huán)境檢測(cè)-重啟(environment detection restart,EDR)策略。通過(guò)對(duì)節(jié)點(diǎn)的環(huán)境信息的監(jiān)測(cè),重啟搜索,添加或減少骨干網(wǎng)絡(luò)中的接入節(jié)點(diǎn),避免節(jié)點(diǎn)回到之前的分組,減少局部搜索陷入循環(huán),直至求出最優(yōu)解。在EDR策略中引入nodemonitor變量,用于存儲(chǔ)節(jié)點(diǎn)是否可以加入最小骨干接入節(jié)點(diǎn)集的信息。當(dāng)nodemonitor為1時(shí),表示該節(jié)點(diǎn)加入骨干接入網(wǎng)絡(luò)中后,重疊區(qū)域的節(jié)點(diǎn)個(gè)數(shù)減少;當(dāng)nodemonitor為0時(shí),表示該節(jié)點(diǎn)不允許加入骨干接入網(wǎng)絡(luò)或者該節(jié)點(diǎn)離開(kāi)骨干接入網(wǎng)絡(luò)后交疊節(jié)點(diǎn)數(shù)減少。在EDR策略中,更新nodemonitor變量須遵守以下規(guī)則:

規(guī)則1初始骨干接入節(jié)點(diǎn)集合中的接入節(jié)點(diǎn)的nodemonitor值為1。

規(guī)則2從骨干接入節(jié)點(diǎn)集合S中移除接入節(jié)點(diǎn)u時(shí),nodemonitor(u)=0,鄰接節(jié)點(diǎn)v,即與u連接的節(jié)點(diǎn)的nodemonitor(v)=1。

規(guī)則3當(dāng)節(jié)點(diǎn)v加入到S后,v的鄰接節(jié)點(diǎn)u的nodemonitor(u)=1。

為了避免局部搜索結(jié)果與之前得到的候選解相同,建立一個(gè)禁忌表forbid_list,用于保護(hù)骨干網(wǎng)絡(luò)中的接入節(jié)點(diǎn)被重復(fù)挑選且forbid_list中的節(jié)點(diǎn)不允許被刪除。優(yōu)化算法流程如圖4所示。

圖4 最小骨干接入節(jié)點(diǎn)集優(yōu)化算法流程

算法首先初始化nodemonitor,forbid_list以及節(jié)點(diǎn)的Nfreq和score,初始值為0,然后通過(guò)迭代添加覆蓋大多數(shù)剩余未覆蓋的節(jié)點(diǎn),直到S覆蓋所有節(jié)點(diǎn),從而貪婪地獲得一個(gè)初始候選解S。在初始化結(jié)束時(shí),最佳解決方案S*由S更新并檢查S是否覆蓋所有頂點(diǎn),通過(guò)EDR策略重復(fù)搜索得到新的解來(lái)更新S*。最后,nodemonitor的值由規(guī)則2更新。

如果當(dāng)前解S存在未覆蓋的節(jié)點(diǎn),算法首先從S中取出score值最高的一個(gè)節(jié)點(diǎn),在未覆蓋的節(jié)點(diǎn)中重新搜索骨干接入節(jié)點(diǎn)。在移除過(guò)程結(jié)束后,算法迭代地將一個(gè)節(jié)點(diǎn)添加到S中,直到它覆蓋所有節(jié)點(diǎn),即候選解是一個(gè)骨干接入節(jié)點(diǎn)集。當(dāng)選擇的未覆蓋節(jié)點(diǎn)被添加到候選解決方案中時(shí),nodemonitor值會(huì)根據(jù)規(guī)則3更新,這個(gè)新添加的節(jié)點(diǎn)會(huì)被添加到forbid_list中。每次添加一個(gè)未覆蓋節(jié)點(diǎn)后,未覆蓋節(jié)點(diǎn)的頻率增加1。當(dāng)搜索時(shí)間截止時(shí),最佳解決辦法即S*。優(yōu)化后的骨干接入網(wǎng)絡(luò)模型如圖5所示。

圖5 優(yōu)化后的骨干接入網(wǎng)絡(luò)模型示意圖

優(yōu)化后的骨干接入網(wǎng)絡(luò)中不僅接入節(jié)點(diǎn)數(shù)量減少,接入子網(wǎng)中的重疊節(jié)點(diǎn)數(shù)量也會(huì)隨之減少,從而減小節(jié)點(diǎn)之間的接入干擾,使接入子網(wǎng)中的節(jié)點(diǎn)有足夠的接入資源向接入節(jié)點(diǎn)發(fā)起接入。

3 窗口控制-前導(dǎo)復(fù)用

通過(guò)建立最小骨干接入節(jié)點(diǎn)集優(yōu)化小區(qū)骨干接入網(wǎng)絡(luò)模型后,針對(duì)第二層接入網(wǎng)中MTC設(shè)備出現(xiàn)在重疊區(qū)域的問(wèn)題,首先根據(jù)各組MTC設(shè)備數(shù)量按比例分配重疊設(shè)備并建立接入子網(wǎng)模型,然后通過(guò)窗口控制和前導(dǎo)碼復(fù)用策略控制MTC設(shè)備向簇頭設(shè)備發(fā)起接入,提高M(jìn)TC設(shè)備的接入成功率和資源利用率。需要注意的是,每一組的MTC設(shè)備接入時(shí)都攜帶有表明分組的標(biāo)識(shí)號(hào),簇頭設(shè)備會(huì)根據(jù)標(biāo)識(shí)號(hào)決定是否發(fā)起接入響應(yīng),防止MTC設(shè)備接入其他組的簇頭設(shè)備導(dǎo)致接入時(shí)延增大和接入資源浪費(fèi),接入網(wǎng)的第二層網(wǎng)絡(luò)模型如圖6所示。

圖6 第二層接入網(wǎng)絡(luò)模型示意圖

通過(guò)網(wǎng)絡(luò)分層對(duì)MTC設(shè)備分組,分組內(nèi)的設(shè)備可能在其他分組內(nèi)也可以通信,即圖6中的重疊設(shè)備。為防止重疊設(shè)備沒(méi)有接入目標(biāo)卻占用了接入資源而造成接入資源浪費(fèi),需要重新分配重疊設(shè)備,重新分配的計(jì)算式為:

(13)

其中:NC(n1),l表示第C組內(nèi)重新分配的重疊設(shè)備數(shù);Nl(n1,n2)是n1和n2分組內(nèi)總的重疊設(shè)備數(shù);NC(n1)和NC(n2)是分組內(nèi)的MTC設(shè)備數(shù),即根據(jù)分組內(nèi)的MTC設(shè)備數(shù)量按比例分配重疊MTC設(shè)備。

重新分配重疊設(shè)備后,MTC設(shè)備向所在組內(nèi)的簇頭設(shè)備發(fā)起接入,同時(shí)通過(guò)前導(dǎo)碼復(fù)用的方法使每個(gè)分組有足夠的接入資源供MTC設(shè)備選擇,可以降低同組MTC設(shè)備因選中同一前導(dǎo)碼導(dǎo)致接入失敗概率,則第k個(gè)前導(dǎo)碼僅被多個(gè)設(shè)備中的一個(gè)設(shè)備選中的概率為

Nc,i=Nc,l+NC(n)

(15)

其中:Nc,i表示第i個(gè)接入時(shí)隙某個(gè)分組的MTC設(shè)備數(shù)量;Nch表示簇頭設(shè)備個(gè)數(shù);M-Nch表示每組可用的前導(dǎo)碼數(shù)量;Sk=1表示第k個(gè)前導(dǎo)碼僅被一個(gè)設(shè)備選中的概率。

第i個(gè)時(shí)隙某組設(shè)備數(shù)量為Nc,i=n時(shí)成功傳輸前導(dǎo)碼的設(shè)備數(shù)量為Yc,i,其期望值為:

(16)

可知,某個(gè)分組內(nèi)當(dāng)前可用前導(dǎo)碼數(shù)量為M-Nch。當(dāng)前時(shí)隙內(nèi)該組嘗試發(fā)起接入的設(shè)備數(shù)量為M-Nch時(shí),則該組每個(gè)時(shí)隙內(nèi)成功接入的設(shè)備數(shù)量最大。為了證明MTC設(shè)備數(shù)量與前導(dǎo)碼數(shù)量相同時(shí)成功接入的設(shè)備數(shù)量最大,由式(16)可得到每個(gè)接入時(shí)隙內(nèi)MTC設(shè)備數(shù)量與成功接入的MTC設(shè)備數(shù)量關(guān)系,具體如圖7所示。

圖7 MTC設(shè)備數(shù)-接入成功數(shù)量關(guān)系

隨著分組內(nèi)每個(gè)接入時(shí)隙內(nèi)設(shè)備數(shù)量的增加,成功接入的設(shè)備數(shù)量會(huì)越來(lái)越少,但是如果能將各分組內(nèi)每個(gè)接入時(shí)隙內(nèi)的嘗試發(fā)起接入的設(shè)備數(shù)量控制為M-Nch,保證小區(qū)內(nèi)每個(gè)接入時(shí)隙成功接入的設(shè)備數(shù)量最大化,則小區(qū)內(nèi)每個(gè)時(shí)隙設(shè)備的接入成功率可以得到提升。

在這種思想基礎(chǔ)上,提出了一種基于窗口控制的接入模型。該模型主要分為3個(gè)部分,分別為等待發(fā)起隨機(jī)接入的設(shè)備隊(duì)列、接入失敗進(jìn)入退避狀態(tài)的設(shè)備隊(duì)列和當(dāng)前窗口內(nèi)發(fā)起隨機(jī)接入的隊(duì)列,具體模型如圖8所示。

圖8 窗口控制接入模型示意圖

分組內(nèi)所有設(shè)備都有一個(gè)分值,該值表示設(shè)備可以與周圍設(shè)備進(jìn)行通信的設(shè)備數(shù)量,即分值越大業(yè)務(wù)越繁忙。小區(qū)MTC設(shè)備按照分值進(jìn)行排序送入窗口,分值越大,優(yōu)先送入窗口中向簇頭設(shè)備發(fā)起接入。圖8中在隨機(jī)接入時(shí)隙到來(lái)前,所有設(shè)備會(huì)根據(jù)分值大小依次排列等待,若退避隊(duì)列中在當(dāng)前時(shí)隙內(nèi)有退避結(jié)束的MTC設(shè)備,則優(yōu)先發(fā)起接入;當(dāng)隨機(jī)接入時(shí)隙來(lái)臨時(shí),處于窗口內(nèi)的MTC設(shè)備向簇頭設(shè)備發(fā)起隨機(jī)接入嘗試。當(dāng)前隨機(jī)接入時(shí)隙結(jié)束時(shí),若窗口內(nèi)的部分MTC設(shè)備接入失敗,則會(huì)隨機(jī)生成一個(gè)退避時(shí)間值并進(jìn)入退避隊(duì)列直至退避結(jié)束才可以再次發(fā)起隨機(jī)接入嘗試,同時(shí)安排符合窗口大小的等待隊(duì)列中的MTC設(shè)備數(shù)量進(jìn)入窗口等待下一個(gè)隨機(jī)接入時(shí)隙。

窗口控制方法和沒(méi)有做任何接入控制的接入成功率計(jì)算式如下:

(17)

(18)

其中:PWin為窗口控制方法的接入成功率;Ns為接入時(shí)隙數(shù)量;Nw,i為每個(gè)接入時(shí)隙發(fā)起接入的MTC設(shè)備數(shù)量;PCom為沒(méi)有做任何控制的接入成功率。

為了解決接入資源緊張問(wèn)題,引入復(fù)用PA方案,使每個(gè)分組內(nèi)的MTC設(shè)備使用相同數(shù)量的前導(dǎo)碼接入簇頭設(shè)備,提升前導(dǎo)碼的利用率。前導(dǎo)碼利用率代表一個(gè)接入時(shí)隙內(nèi)每個(gè)前導(dǎo)碼可以接入的MTC設(shè)備數(shù)量[18]。PA利用率計(jì)算式為

(19)

其中:Nk,i為第i個(gè)接入時(shí)隙成功接入的前導(dǎo)碼數(shù)量;nc,i為某個(gè)分組第i個(gè)接入時(shí)隙成功接入的前導(dǎo)碼數(shù)量。為了確保簇頭設(shè)備準(zhǔn)確識(shí)別接入設(shè)備信息,每個(gè)MTC設(shè)備在發(fā)起接入請(qǐng)求時(shí)會(huì)議攜帶分組標(biāo)識(shí)號(hào)Gid。簇頭設(shè)備在接收MTC設(shè)備發(fā)來(lái)的接入請(qǐng)求時(shí),會(huì)將自身的標(biāo)識(shí)號(hào)與發(fā)起接入設(shè)備的分組標(biāo)識(shí)號(hào)匹配,匹配結(jié)果表示為

(20)

其中:Chid為簇頭設(shè)備的標(biāo)識(shí)號(hào);rec為發(fā)起接入設(shè)備與簇頭設(shè)備的標(biāo)識(shí)號(hào)是否相同,相同則表示該接入設(shè)備與簇頭設(shè)備在同一分組,允許該設(shè)備向標(biāo)識(shí)號(hào)為Chid的簇頭設(shè)備發(fā)起接入。

4 仿真分析

為了驗(yàn)證本文算法的優(yōu)勢(shì),通過(guò)Matlab進(jìn)行仿真實(shí)驗(yàn),并將本文算法與其他算法的性能進(jìn)行對(duì)比。首先對(duì)網(wǎng)絡(luò)分層算法進(jìn)行了仿真實(shí)驗(yàn),對(duì)分組數(shù)量和重疊設(shè)備數(shù)量進(jìn)行比較,其次在網(wǎng)絡(luò)分層的基礎(chǔ)上實(shí)現(xiàn)了對(duì)窗口控制和前導(dǎo)復(fù)用相結(jié)合的仿真實(shí)驗(yàn),最后對(duì)設(shè)備接入成功率和整體接入時(shí)隙比較驗(yàn)證,仿真參數(shù)設(shè)置如表1所示。

表1 仿真參數(shù)設(shè)置

為不失一般性,仿真實(shí)驗(yàn)次數(shù)設(shè)置成50次,所有實(shí)驗(yàn)數(shù)據(jù)取均值。網(wǎng)絡(luò)分層的對(duì)比算法為隨機(jī)搜索算法、最小ID算法、最大拓?fù)涠人惴╗20],其中TA取值為6。針對(duì)設(shè)備接入引入了ACB機(jī)制、動(dòng)態(tài)ACB機(jī)制、分層+ACB算法、窗口控制接入算法進(jìn)行性能比對(duì)。本文算法在網(wǎng)絡(luò)分層與接入控制方面對(duì)比算法的時(shí)間復(fù)雜度見(jiàn)表2。

表2 算法時(shí)間復(fù)雜度

本文算法時(shí)間復(fù)雜度主要表現(xiàn)在建立初始骨干接入網(wǎng)絡(luò)模型和求最小骨干接入節(jié)點(diǎn)集合上,需要N3+N2+N輪搜索,其中N為節(jié)點(diǎn)個(gè)數(shù)。

隨著MTC設(shè)備數(shù)量的增加,不同算法分組數(shù)量變化情況如圖9所示。可以看出,隨著MTC設(shè)備數(shù)量的增加,3種對(duì)比算法的分組數(shù)量都在逐漸增加,而本文所提出的分層優(yōu)化算法始終保持在9組,表明優(yōu)化算法隨著設(shè)備的個(gè)數(shù)增加分組已經(jīng)飽和,有較好的收斂性;從分組數(shù)量來(lái)看,本文所提出的網(wǎng)絡(luò)分層算法分組數(shù)比最小ID算法平均減少43%,比初始分層算法減少47%,比最大拓?fù)涠人惴p少48%,說(shuō)明本文所提出的網(wǎng)絡(luò)分層優(yōu)化算法能有效降低分組數(shù)量,使得后續(xù)接入時(shí)有足夠多的前導(dǎo)碼資源。因?yàn)楸疚乃惴ㄒ隕DR策略的目的是以最小的節(jié)點(diǎn)覆蓋同一區(qū)域內(nèi)的整個(gè)網(wǎng)絡(luò),隨著MTC設(shè)備數(shù)量增加,會(huì)導(dǎo)致每個(gè)分組內(nèi)的設(shè)備數(shù)量增加,但并不會(huì)影響分組數(shù)量。

圖9 網(wǎng)絡(luò)分層算法性能

圖10為不同網(wǎng)絡(luò)分層算法隨著MTC設(shè)備數(shù)量的增加處于重疊區(qū)域的MTC設(shè)備數(shù)量的變化情況。隨著MTC設(shè)備數(shù)量的增加,網(wǎng)絡(luò)分層優(yōu)化算法和3種對(duì)比算法的交疊設(shè)備數(shù)量都在遞增。從重疊區(qū)域的MTC設(shè)備數(shù)量來(lái)看,網(wǎng)絡(luò)分層優(yōu)化算法的重疊MTC設(shè)備數(shù)量最少,比最小ID算法減少59.24%,比最大拓?fù)涠人惴ㄆ骄鶞p少65.41%,隨機(jī)搜索算法平均減少64.8%,說(shuō)明本文算法在接入時(shí)MTC設(shè)備間的干擾情況較好。從重疊的MTC設(shè)備增加趨勢(shì)來(lái)看,網(wǎng)絡(luò)分層優(yōu)化算法增加得更為緩慢,對(duì)其重新分配時(shí)需要的運(yùn)算量和對(duì)后續(xù)接入的影響也更小。

圖10 網(wǎng)絡(luò)分層算法的重疊MTC設(shè)備數(shù)

圖11為所有MTC設(shè)備在50個(gè)接入時(shí)隙內(nèi)隨著MTC設(shè)備數(shù)量增加,不同算法接入成功率的變化情況。可以看出,隨著MTC設(shè)備數(shù)量的增加,ACB算法、動(dòng)態(tài)ACB算法和窗口控制算法的接入成功率都在減小,而網(wǎng)絡(luò)分層與ACB結(jié)合算法和本文算法的接入成功率基本保持不變。ACB算法和動(dòng)態(tài)ACB算法性能最差,接入成功率最高為27.28%;隨著MTC設(shè)備數(shù)量增加,窗口控制算法的接入成功率相比于最初減小了31%;網(wǎng)絡(luò)分層與ACB相結(jié)合的算法的接入成功率始終保持在98%～99%,不能保證所有MTC設(shè)備成功接入網(wǎng)絡(luò);本文算法的接入成功率為100%,可以保證2 000個(gè)MTC設(shè)備都能成功接入。相比4種對(duì)比算法中所有MTC設(shè)備在同一接入時(shí)隙內(nèi)發(fā)起接入的情況,本文通過(guò)網(wǎng)絡(luò)分層算法實(shí)現(xiàn)MTC設(shè)備分組接入,降低了同一接入時(shí)隙內(nèi)的接入沖突數(shù)量,每個(gè)分組的MTC設(shè)備通過(guò)窗口控制接入對(duì)應(yīng)分組的簇頭設(shè)備,使得每個(gè)接入時(shí)隙的成功接入設(shè)備數(shù)量最大化。

圖11 50個(gè)接入時(shí)隙的接入成功率

圖12是不同接入算法隨著MTC設(shè)備數(shù)量增加接入所需時(shí)隙個(gè)數(shù)變化的情況。可以看到,4種對(duì)比算法中性能最好的是窗口控制算法,2 000個(gè)設(shè)備接入需要約87.22個(gè)接入時(shí)隙,性能最差的是ACB算法,需要434個(gè)接入時(shí)隙才能使小區(qū)設(shè)備全部接入網(wǎng)絡(luò),而本文提出的算法隨著MTC數(shù)量的增加,其接入時(shí)隙個(gè)數(shù)始終保持在8～11個(gè)接入時(shí)隙內(nèi),比窗口控制算法平均降低了85%。這是因?yàn)楸疚乃惴ㄍㄟ^(guò)窗口控制和前導(dǎo)碼復(fù)用的方法對(duì)第二層網(wǎng)絡(luò)中的設(shè)備進(jìn)行控制,相比于窗口控制算法,每個(gè)接入時(shí)隙只能允許M-Nch個(gè)設(shè)備接入,每個(gè)接入時(shí)隙允許發(fā)起接入的設(shè)備數(shù)量是窗口控制算法的Nch倍,提高了整體MTC設(shè)備的接入效率。

圖12 設(shè)備接入所需時(shí)隙個(gè)數(shù)

圖13是不同接入算法隨著MTC設(shè)備數(shù)量增加PA利用率的變化情況。ACB算法和動(dòng)態(tài)ACB算法的PA利用率最低,因?yàn)?種對(duì)比算法對(duì)MTC設(shè)備的接入控制能力有限,不能滿足大量MTC設(shè)備的接入需求;窗口控制算法的PA利用率隨著MTC設(shè)備數(shù)量的增加始終保持在36%～38%;分層和ACB相結(jié)合算法的PA利用率始終保持在77%～78%;本文所提算法的PA利用率一直保持在98%左右,比窗口控制算法提高60%,比分層和ACB算法提高20%。這是因?yàn)楸疚乃惴ㄒ肓薖A復(fù)用方案,不同分組內(nèi)的MTC設(shè)備在同一接入時(shí)隙有足夠的前導(dǎo)資源進(jìn)行接入,使一個(gè)前導(dǎo)資源可接入的設(shè)備數(shù)量增多。

圖13 PA利用率

5 結(jié)論

提出了一種網(wǎng)絡(luò)分層優(yōu)化結(jié)合窗口控制的方法來(lái)控制每個(gè)接入時(shí)隙發(fā)起接入請(qǐng)求的設(shè)備數(shù)量,提高M(jìn)TC設(shè)備接入成功率。通過(guò)網(wǎng)絡(luò)分層優(yōu)化算法對(duì)MTC設(shè)備進(jìn)行分組,然后每組會(huì)選出一個(gè)簇頭設(shè)備,簇頭設(shè)備接入基站后充當(dāng)其余MTC設(shè)備與基站之間的中繼設(shè)備,負(fù)責(zé)接收所在小組內(nèi)的其余設(shè)備的接入請(qǐng)求,同時(shí)其余MTC設(shè)備通過(guò)窗口控制算法和前導(dǎo)碼復(fù)用的方法向簇頭設(shè)備發(fā)起接入。仿真結(jié)果表明,本文算法可以使MTC設(shè)備的接入成功率達(dá)到100%,接入時(shí)延相比窗口控制算法降低85%左右,有效緩解了M2M通信設(shè)備接入沖突的情況,降低了小區(qū)整體設(shè)備的接入時(shí)延。未來(lái)將利用深度學(xué)習(xí)或強(qiáng)化學(xué)習(xí)等算法與本文算法相結(jié)合,通過(guò)感知MTC設(shè)備數(shù)量來(lái)解決邊緣稀疏設(shè)備的接入問(wèn)題。