面向M2M通信的网络分层与窗口控制接入策略

李姣军,杨 川,杨 凡,喻 涛,杜源昌,陈征骥

(1.重庆理工大学 电气与电子工程学院, 重庆 400054;2.重庆川仪自动化股份有限公司, 重庆 400700)

0 引言

随着无线通信技术的发展,5G通信技术更加成熟,为机器与机器(machine to machine,M2M)通信提供了很好的技术支持。M2M通信同人与人(human to human,H2H)之间的通信相似,机器类型通信(machine type communication,MTC)设备在实现通信功能之前,需要完成随机接入过程与基站建立连接。但是MTC设备的部署密集程度远超一般通信设备的部署密集程度[1],导致海量设备在接入时因MTC设备间的通信干扰更容易引起接入冲突。另一方面,由于MTC设备数量多、接入资源紧张,因此当大量MTC设备同时向基站发起接入时,必然会使得部分MTC设备因选中相同的接入资源而导致接入冲突,严重时造成网络拥塞,使所有MTC设备接入失败[2]。

为缓解大规模机器类通信中接入冲突、网络拥塞的问题,国内外提出了多种随机接入控制策略,主要包括接入控制限制(access control barring,ACB)、退避指示(backoff indictor,BI)、动态ACB等方法[3]。ACB控制方案本质是给MTC设备和基站分配一个ACB因子,若MTC设备的ACB因子小于基站的ACB因子,则允许该设备发起接入,反之则不允许发起接入,从而降低每个接入机会(random access opportunities,RO)上发起接入的设备数量。动态ACB方案根据预测的接入设备数量来调整ACB因子大小。文献[4-6]中通过调整ACB参数控制每个随机接入时隙中的发起接入设备数量,但该方案只适用于设备数量较少的情况。Zhou等[7]通过将ACB机制与资源分配相结合来提高小区内接入吞吐量,解决了随机接入拥塞的问题,但接入时延较高。文献[8-9]提出的动态ACB是根据每个接入时隙活跃的设备数量来估计ACB因子,但现有估计算法比较简单,不能使接入吞吐量性能达到最佳。BI算法是在设备发起接入请求后没有收到基站的接入响应(random access response,RAR)时,基站会给设备分配一个BI值,使设备在等待一段时间后重新发起接入以缓解接入冲突。Xu等[10]中提出的退避方案,通过给每个设备随机分配一个退避时间从而达到缓解冲突的目的,但是退避时间会导致接入时延较高。孙君等[11]在ACB控制的基础上提出一种基于退避预测的动态ACB控制方案来降低接入冲突,但该方案只适用于环境简单、设备数量较少的场景。综上所述,上述大部分接入控制方案只适用接入设备数量较少的场景,或者接入所需时延较高,无法满足MTC设备大规模接入的需求。

网络分层是目前解决MTC设备部署密集而引起接入冲突的主要手段。网络分层通过将小区内的MTC设备分配到不同分组内,简化小区接入网的网络结构,从而降低小区内的设备接入冲突数量。刘冬雪等[12]提出一种分层接入的方法来提高接入资源的利用率和接入成功率,但未考虑MTC设备同时出现在多个分组内的情况,导致MTC设备找不到接入对象,增加了算法的复杂度。Jang等[13]提出根据业务到达率对小区设备分组和按照每个分组内请求接入的数量分配前导码,但该方法接入时延较高。文献[14-15]提出k邻近算法对不同MTC设备按照聚类进行分层,但该算法针对小区边缘MTC设备,且要求分层间的资源两两正交,不适合应用于资源紧张的接入网。邵羽丰等[16]提出了一种基于网络分层的ACB控制方案提高了接入成功率,但该方案由于ACB因子的随机性,会导致接入时延较高。李军等[17]提出了采用滑动窗口控制的方法来控制每个接入时隙发起接入的设备数量,提高了接入成功率,降低了平均接入时延,但未考虑接入资源不足的问题。以上方案均只考虑了降低每个接入时隙的设备数量和接入冲突,没有考虑接入资源与接入时延带来的影响,很难支撑大规模机器类通信随机接入的需求。

为了解决大规模M2M通信网络拥塞、接入时延高的问题,提出一种网络分层技术结合窗口控制技术的算法。首先建立骨干接入网络模型,提出接入网络分层优化算法,优化骨干接入节点集合,集合中的接入节点代表了簇头设备,实现网络分层。通过建立骨干接入网络模型和接入子网模型,提出了窗口控制和前导码复用策略,实现对MTC设备的接入控制。该方法可以使每个接入时隙内成功接入的设备数量最大化,降低设备接入冲突和接入时延,从而提高小区的接入成功率。

1 系统模型

系统模型如图1所示,通信基站位于小区中心,负责接收小区内所有MTC设备的随机接入请求,并将MTC设备接入网络。小区中有M个可用前导码(preamble,PA),N个MTC设备随机分布在小区内,其中MTC设备主要分为水电抄表、智能家居设备、远程监测设备等静态分布设备。

图1 系统模型示意图

由于MTC设备通过竞争型随机接入方式向基站发起接入请求,且设备部署量庞大,当大量MTC设备突然涌入网络并向基站发起随机接入请求时,必然会因为有限的接入资源竞争而引起接入冲突,甚至导致小区网络拥塞。针对MTC设备接入冲突问题,用无向图G=(V,E)来表示MTC设备间的通信关系。其中V表示节点集合,E为边集合,节点和边分别代表了MTC设备和MTC设备之间的通信链路,用邻接矩阵A表示节点之间的通信关系。

2 网络分层算法

在随机接入过程的第一步中,MTC设备向基站发送PA。MTC设备可选择的PA数量有限[18],最多不超过64个。多个MTC设备在同一接入时隙向基站发起接入引起前导码碰撞,这种情况视为随机接入发起失败,因此为提高小区内MTC设备的接入成功率,使用网络分层来减少在同一接入时隙内选择相同PA的MTC设备数量。

通过分层接入的思想使MTC设备分组接入,建立骨干接入网络模型,解决接入资源不足的问题。首先,对小区MTC设备分组时,需要根据MTC的通信范围和位置,作出小区接入网的网络拓扑图;在得到网络拓扑图后,利用定时提前量(timing advance,TA)分组并建立骨干接入网络,考虑到接入资源紧张,提出最小骨干接入节点集算法,进一步减少骨干接入网络中的接入节点数量,优化骨干接入网络;为了保证MTC设备之间、MTC设备与基站的通信质量,在建立骨干接入网络模型时需要考虑节点之间的距离,需要以最少的接入节点数量覆盖整个网络,同时每个接入节点所管理的节点数不能相差太大,并减少节点被多个接入节点管理的次数,否则会造成接入资源浪费[19]。

2.1 初始分层-建立骨干接入网络模型

根据MTC设备之间的通信关系得到小区通信网络的无向拓扑图G,如图2所示,小区中的每个MTC设备对应图2中的节点V,任意2个可以互相通信的节点相连构成边E。

图2 小区的无向接入网络拓扑图

网络拓扑图中边的长度为节点之间的距离,设节点Vi和Vj的坐标分别为(xi,yi)、(xj,yj),则节点Vi与节点Vj之间的欧式距离为

(1)

为了保证节点之间的通信质量,节点间的物理距离应该小于通信距离。d是判断每个节点是否可以通信的阈值,则每个节点之间的通信关系可以表示成:

(2)

其中Oij=1表示节点Vi与节点Vj可以通信。d根据TA与物理距离之间的关系计算,计算式为

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

(3)

DTA=16×c×Ts/2

(4)

Ts=1/(SCS×NFFT)

(5)

其中:c是光速;SCS表示子载波间隔;NFFT表示FFT运算点数。由式(2)可以得到整个小区MTC设备接入网的邻接矩阵为

(6)

由式(6)中的邻接矩阵可作出小区接入网的网络拓扑图,然后在网络拓扑图的基础上求解骨干接入节点集,骨干接入节点集数学表示方法为:

(7)

其中:V为节点集合;S为骨干节点集合;N(u)为节点u的一跳邻接节点集合。

当节点在网络拓扑图中都处于初始状态时,即MTC设备处于开机未接入的状态,算法随机选择开始节点,它们向自己的相邻节点发送握手消息,并统计自己接收的握手消息中的分值信息。然后,在由起始节点和它的相邻节点组成的网络中,将分值最大的节点设置为初始节点并添加到初始解S中,分值计算式为:

(8)

其中:score(u)为节点u的分值;S为骨干节点的集合;C1是将u加入S后由未被覆盖变为被覆盖的节点的集合,C2是通过将u从S中移除由被覆盖变为未被覆盖的节点的集合;Nfreq表示每个节点的频率值。每个节点的初始频率值被设置为1,通过不断局部搜索迭代更新Nfreq,每一次没有被覆盖的节点的Nfreq增加1,节点的Nfreq越大,被选为骨干节点的概率就越大。小区初始骨干接入网建立具体步骤如下:

步骤1随机选择节点v向其相邻节点发送握手消息,统计分值信息并建立小区的网络拓扑图;

步骤2对节点v及其相邻节点的分值进行比较,选择分值最大的节点u加入候选解S,作为骨干接入节点;

步骤3将节点u及其单跳邻接节点的编号从节点集合中去除;

步骤4在剩余节点中重复步骤2和3,直到所有节点都被覆盖;

步骤5选择出的骨干接入节点构成的网络就是初始骨干网络。

通过建立小区初始骨干接入网络对小区的接入网络实现简化。然而,初始骨干网络中的接入节点数目较多,一些节点存在被多个接入节点支配的情况,还需要对网络进一步优化,初始骨干接入网络模型如图3所示。

图3 初始骨干接入网络模型示意图

初始骨干接入网络模型中的节点V和重叠节点组成第二层网络-接入子网。其中,节点V可以直接向其所属的接入节点发起接入,而重叠节点可以向多个接入节点发起接入,会对节点V造成接入干扰。

2.2 分层优化-最小骨干接入节点集

初始骨干接入网络中的骨干接入节点个数较多,为了使普通节点有足够的接入资源,需要简化初始骨干接入网络,通过不断优化找出最小骨干接入节点集,即以最少的骨干接入节点覆盖整个网络。

根据最小骨干接入节点集的定义及满足条件,建立最小骨干接入节点集的数学模型。最小骨干接入节点集的数学模型表示为

(9)

(10)

11)

(12)

其中:CBN表示求解最小骨干接入节点集合;Cm表示节点之间的通信关系,在降低骨干接入节点支配区域的重叠范围时,其约束条件为节点是接入节点或邻接节点;n表示节点数量。

为了防止局部搜索出来的解是局部最优解,引入了环境检测-重启(environment detection restart,EDR)策略。通过对节点的环境信息的监测,重启搜索,添加或减少骨干网络中的接入节点,避免节点回到之前的分组,减少局部搜索陷入循环,直至求出最优解。在EDR策略中引入nodemonitor变量,用于存储节点是否可以加入最小骨干接入节点集的信息。当nodemonitor为1时,表示该节点加入骨干接入网络中后,重叠区域的节点个数减少;当nodemonitor为0时,表示该节点不允许加入骨干接入网络或者该节点离开骨干接入网络后交叠节点数减少。在EDR策略中,更新nodemonitor变量须遵守以下规则:

规则1初始骨干接入节点集合中的接入节点的nodemonitor值为1。

规则2从骨干接入节点集合S中移除接入节点u时,nodemonitor(u)=0,邻接节点v,即与u连接的节点的nodemonitor(v)=1。

规则3当节点v加入到S后,v的邻接节点u的nodemonitor(u)=1。

为了避免局部搜索结果与之前得到的候选解相同,建立一个禁忌表forbid_list,用于保护骨干网络中的接入节点被重复挑选且forbid_list中的节点不允许被删除。优化算法流程如图4所示。

图4 最小骨干接入节点集优化算法流程

算法首先初始化nodemonitor,forbid_list以及节点的Nfreq和score,初始值为0,然后通过迭代添加覆盖大多数剩余未覆盖的节点,直到S覆盖所有节点,从而贪婪地获得一个初始候选解S。在初始化结束时,最佳解决方案S*由S更新并检查S是否覆盖所有顶点,通过EDR策略重复搜索得到新的解来更新S*。最后,nodemonitor的值由规则2更新。

如果当前解S存在未覆盖的节点,算法首先从S中取出score值最高的一个节点,在未覆盖的节点中重新搜索骨干接入节点。在移除过程结束后,算法迭代地将一个节点添加到S中,直到它覆盖所有节点,即候选解是一个骨干接入节点集。当选择的未覆盖节点被添加到候选解决方案中时,nodemonitor值会根据规则3更新,这个新添加的节点会被添加到forbid_list中。每次添加一个未覆盖节点后,未覆盖节点的频率增加1。当搜索时间截止时,最佳解决办法即S*。优化后的骨干接入网络模型如图5所示。

图5 优化后的骨干接入网络模型示意图

优化后的骨干接入网络中不仅接入节点数量减少,接入子网中的重叠节点数量也会随之减少,从而减小节点之间的接入干扰,使接入子网中的节点有足够的接入资源向接入节点发起接入。

3 窗口控制-前导复用

通过建立最小骨干接入节点集优化小区骨干接入网络模型后,针对第二层接入网中MTC设备出现在重叠区域的问题,首先根据各组MTC设备数量按比例分配重叠设备并建立接入子网模型,然后通过窗口控制和前导码复用策略控制MTC设备向簇头设备发起接入,提高MTC设备的接入成功率和资源利用率。需要注意的是,每一组的MTC设备接入时都携带有表明分组的标识号,簇头设备会根据标识号决定是否发起接入响应,防止MTC设备接入其他组的簇头设备导致接入时延增大和接入资源浪费,接入网的第二层网络模型如图6所示。

图6 第二层接入网络模型示意图

通过网络分层对MTC设备分组,分组内的设备可能在其他分组内也可以通信,即图6中的重叠设备。为防止重叠设备没有接入目标却占用了接入资源而造成接入资源浪费,需要重新分配重叠设备,重新分配的计算式为:

(13)

其中:NC(n1),l表示第C组内重新分配的重叠设备数;Nl(n1,n2)是n1和n2分组内总的重叠设备数;NC(n1)和NC(n2)是分组内的MTC设备数,即根据分组内的MTC设备数量按比例分配重叠MTC设备。

重新分配重叠设备后,MTC设备向所在组内的簇头设备发起接入,同时通过前导码复用的方法使每个分组有足够的接入资源供MTC设备选择,可以降低同组MTC设备因选中同一前导码导致接入失败概率,则第k个前导码仅被多个设备中的一个设备选中的概率为

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

(15)

其中:Nc,i表示第i个接入时隙某个分组的MTC设备数量;Nch表示簇头设备个数;M-Nch表示每组可用的前导码数量;Sk=1表示第k个前导码仅被一个设备选中的概率。

第i个时隙某组设备数量为Nc,i=n时成功传输前导码的设备数量为Yc,i,其期望值为:

(16)

可知,某个分组内当前可用前导码数量为M-Nch。当前时隙内该组尝试发起接入的设备数量为M-Nch时,则该组每个时隙内成功接入的设备数量最大。为了证明MTC设备数量与前导码数量相同时成功接入的设备数量最大,由式(16)可得到每个接入时隙内MTC设备数量与成功接入的MTC设备数量关系,具体如图7所示。

图7 MTC设备数-接入成功数量关系

随着分组内每个接入时隙内设备数量的增加,成功接入的设备数量会越来越少,但是如果能将各分组内每个接入时隙内的尝试发起接入的设备数量控制为M-Nch,保证小区内每个接入时隙成功接入的设备数量最大化,则小区内每个时隙设备的接入成功率可以得到提升。

在这种思想基础上,提出了一种基于窗口控制的接入模型。该模型主要分为3个部分,分别为等待发起随机接入的设备队列、接入失败进入退避状态的设备队列和当前窗口内发起随机接入的队列,具体模型如图8所示。

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

分组内所有设备都有一个分值,该值表示设备可以与周围设备进行通信的设备数量,即分值越大业务越繁忙。小区MTC设备按照分值进行排序送入窗口,分值越大,优先送入窗口中向簇头设备发起接入。图8中在随机接入时隙到来前,所有设备会根据分值大小依次排列等待,若退避队列中在当前时隙内有退避结束的MTC设备,则优先发起接入;当随机接入时隙来临时,处于窗口内的MTC设备向簇头设备发起随机接入尝试。当前随机接入时隙结束时,若窗口内的部分MTC设备接入失败,则会随机生成一个退避时间值并进入退避队列直至退避结束才可以再次发起随机接入尝试,同时安排符合窗口大小的等待队列中的MTC设备数量进入窗口等待下一个随机接入时隙。

窗口控制方法和没有做任何接入控制的接入成功率计算式如下:

(17)

(18)

其中:PWin为窗口控制方法的接入成功率;Ns为接入时隙数量;Nw,i为每个接入时隙发起接入的MTC设备数量;PCom为没有做任何控制的接入成功率。

为了解决接入资源紧张问题,引入复用PA方案,使每个分组内的MTC设备使用相同数量的前导码接入簇头设备,提升前导码的利用率。前导码利用率代表一个接入时隙内每个前导码可以接入的MTC设备数量[18]。PA利用率计算式为

(19)

其中:Nk,i为第i个接入时隙成功接入的前导码数量;nc,i为某个分组第i个接入时隙成功接入的前导码数量。为了确保簇头设备准确识别接入设备信息,每个MTC设备在发起接入请求时会议携带分组标识号Gid。簇头设备在接收MTC设备发来的接入请求时,会将自身的标识号与发起接入设备的分组标识号匹配,匹配结果表示为

(20)

其中:Chid为簇头设备的标识号;rec为发起接入设备与簇头设备的标识号是否相同,相同则表示该接入设备与簇头设备在同一分组,允许该设备向标识号为Chid的簇头设备发起接入。

4 仿真分析

为了验证本文算法的优势,通过Matlab进行仿真实验,并将本文算法与其他算法的性能进行对比。首先对网络分层算法进行了仿真实验,对分组数量和重叠设备数量进行比较,其次在网络分层的基础上实现了对窗口控制和前导复用相结合的仿真实验,最后对设备接入成功率和整体接入时隙比较验证,仿真参数设置如表1所示。

表1 仿真参数设置

为不失一般性,仿真实验次数设置成50次,所有实验数据取均值。网络分层的对比算法为随机搜索算法、最小ID算法、最大拓扑度算法[20],其中TA取值为6。针对设备接入引入了ACB机制、动态ACB机制、分层+ACB算法、窗口控制接入算法进行性能比对。本文算法在网络分层与接入控制方面对比算法的时间复杂度见表2。

表2 算法时间复杂度

本文算法时间复杂度主要表现在建立初始骨干接入网络模型和求最小骨干接入节点集合上,需要N3+N2+N轮搜索,其中N为节点个数。

随着MTC设备数量的增加,不同算法分组数量变化情况如图9所示。可以看出,随着MTC设备数量的增加,3种对比算法的分组数量都在逐渐增加,而本文所提出的分层优化算法始终保持在9组,表明优化算法随着设备的个数增加分组已经饱和,有较好的收敛性;从分组数量来看,本文所提出的网络分层算法分组数比最小ID算法平均减少43%,比初始分层算法减少47%,比最大拓扑度算法减少48%,说明本文所提出的网络分层优化算法能有效降低分组数量,使得后续接入时有足够多的前导码资源。因为本文算法引入EDR策略的目的是以最小的节点覆盖同一区域内的整个网络,随着MTC设备数量增加,会导致每个分组内的设备数量增加,但并不会影响分组数量。

图9 网络分层算法性能

图10为不同网络分层算法随着MTC设备数量的增加处于重叠区域的MTC设备数量的变化情况。随着MTC设备数量的增加,网络分层优化算法和3种对比算法的交叠设备数量都在递增。从重叠区域的MTC设备数量来看,网络分层优化算法的重叠MTC设备数量最少,比最小ID算法减少59.24%,比最大拓扑度算法平均减少65.41%,随机搜索算法平均减少64.8%,说明本文算法在接入时MTC设备间的干扰情况较好。从重叠的MTC设备增加趋势来看,网络分层优化算法增加得更为缓慢,对其重新分配时需要的运算量和对后续接入的影响也更小。

图10 网络分层算法的重叠MTC设备数

图11为所有MTC设备在50个接入时隙内随着MTC设备数量增加,不同算法接入成功率的变化情况。可以看出,随着MTC设备数量的增加,ACB算法、动态ACB算法和窗口控制算法的接入成功率都在减小,而网络分层与ACB结合算法和本文算法的接入成功率基本保持不变。ACB算法和动态ACB算法性能最差,接入成功率最高为27.28%;随着MTC设备数量增加,窗口控制算法的接入成功率相比于最初减小了31%;网络分层与ACB相结合的算法的接入成功率始终保持在98%～99%,不能保证所有MTC设备成功接入网络;本文算法的接入成功率为100%,可以保证2 000个MTC设备都能成功接入。相比4种对比算法中所有MTC设备在同一接入时隙内发起接入的情况,本文通过网络分层算法实现MTC设备分组接入,降低了同一接入时隙内的接入冲突数量,每个分组的MTC设备通过窗口控制接入对应分组的簇头设备,使得每个接入时隙的成功接入设备数量最大化。

图11 50个接入时隙的接入成功率

图12是不同接入算法随着MTC设备数量增加接入所需时隙个数变化的情况。可以看到,4种对比算法中性能最好的是窗口控制算法,2 000个设备接入需要约87.22个接入时隙,性能最差的是ACB算法,需要434个接入时隙才能使小区设备全部接入网络,而本文提出的算法随着MTC数量的增加,其接入时隙个数始终保持在8～11个接入时隙内,比窗口控制算法平均降低了85%。这是因为本文算法通过窗口控制和前导码复用的方法对第二层网络中的设备进行控制,相比于窗口控制算法,每个接入时隙只能允许M-Nch个设备接入,每个接入时隙允许发起接入的设备数量是窗口控制算法的Nch倍,提高了整体MTC设备的接入效率。

图12 设备接入所需时隙个数

图13是不同接入算法随着MTC设备数量增加PA利用率的变化情况。ACB算法和动态ACB算法的PA利用率最低,因为2种对比算法对MTC设备的接入控制能力有限,不能满足大量MTC设备的接入需求;窗口控制算法的PA利用率随着MTC设备数量的增加始终保持在36%～38%;分层和ACB相结合算法的PA利用率始终保持在77%～78%;本文所提算法的PA利用率一直保持在98%左右,比窗口控制算法提高60%,比分层和ACB算法提高20%。这是因为本文算法引入了PA复用方案,不同分组内的MTC设备在同一接入时隙有足够的前导资源进行接入,使一个前导资源可接入的设备数量增多。

图13 PA利用率

5 结论

提出了一种网络分层优化结合窗口控制的方法来控制每个接入时隙发起接入请求的设备数量,提高MTC设备接入成功率。通过网络分层优化算法对MTC设备进行分组,然后每组会选出一个簇头设备,簇头设备接入基站后充当其余MTC设备与基站之间的中继设备,负责接收所在小组内的其余设备的接入请求,同时其余MTC设备通过窗口控制算法和前导码复用的方法向簇头设备发起接入。仿真结果表明,本文算法可以使MTC设备的接入成功率达到100%,接入时延相比窗口控制算法降低85%左右,有效缓解了M2M通信设备接入冲突的情况,降低了小区整体设备的接入时延。未来将利用深度学习或强化学习等算法与本文算法相结合,通过感知MTC设备数量来解决边缘稀疏设备的接入问题。