为解决Ad-Hoc多源端和多目的端场景下已有的传输群调度机制通信冲突严重的问题, 分析了Ad-Hoc网络中多对多场景下传输群中不同传输区域发生事件F和事件F'k(k=2, 3, 4) 的概率, 在基于两跳的f-cast中继算法的基础上设计了一种适用于多对多场景下的传输群调度机制, 该传输机制根据上述两种事件发生的概率来调整相应区域内小区成为可通信小区的概率.理论分析和仿真结果表明, 提出的传输群通信调度机制在多对多通信场景下可以有效地减少通信冲突发生的概率, 提高网络通信能力.
Communication conflicts caused by the existing transmission group scheduling mechanism result in reducing network capacity and increasing delay under the multi-source and multi-destination scenario in Ad-Hoc network. To solve the problem, the probability of two events named F and F'k(k=2, 3, 4) was analyzed. And then, a new transmission-group scheduling mechanism was proposed based on two-hop relay algorithm with f-cast to suit for the multi-source and multi-destination scenario. The proposed transmission mechanism adjusts the probability of turning the internal cell in the transmission-group into the communication cell by means of the probability of two kind of events mentioned above. Analysis and simulation show that the transmission group communication scheduling mechanism proposed can effectively reduce the probability of communication conflict under multi-source and multi-destinations, and is beneficial to improve the network capacity.
Ad-Hoc网络中，要保证所有节点可以同时在网络中通信就必须把端点间的干扰降低到一定的限度，以减小网络延迟和提高网络容量. Gupta等[1]研究了无线网络的容量问题，定义了一种可以保证端到端成功通信的传输协议模型.基于此模型，Grossglauser等[2]提出了两跳(two-hop)中继算法，Liu等[3]进而提出了一种基于两跳的至多由f个不同中继端点转发的中继算法(f-cast算法)，设计了相应的通信调度机制. Liu等[4-6]又在此基础上研究了节点的吞吐能力和传输能力对网络容量的影响及最优化转发问题. Wang等[7]提出了两跳中继算法的网络延迟建模方案. Wang等[8]在f-cast的基础上研究了相关游走模型对容量的影响. Liu等[3]提出的传输群调度机制只涉及单源端和单目的端的通信，并没有考虑多源端和多目的端通信的情况.而研究节点通信能力有限(接收端无法同时接收多个发送端发来的信息)的多对多通信场景的通信问题可以为研究实际网络中具有更高效能的端到端通信机制提供更好的理论指导.笔者通过分析发现，在多对多场景下直接应用传输群调度机制会发生较多的通信冲突.故在原有基础上设计了一种可以减少多对多场景下通信冲突的传输群调度机制.
1 网络模型假设n个移动节点处于一个单位为1的网络区域内，区域划分成n个边长为
节点与处于其有效通信范围内的节点通信，每时隙传输群中的节点通过频谱抢占机制抢占通信权限来发送信息.抢占频谱分为2步：第1步，节点所在小区被选为可通信小区；第2步，小区内节点抢占该小区的频谱.如果相邻小区有目标节点，节点则直接向其交付信息；如果无目标节点，节点可以寻找可中继节点并将信息转发给它.
当多个源端与多个目标端同时通信时，原有的传输群通信调度机制可能会发生两种通信冲突事件，即事件F和事件F′k(k=2, 3, 4).事件F指目标端点同时位于几个获得有效通信频谱的端点的有效通信范围内的事件.事件F′k(k=2, 3, 4) 指k个源端同时抢占少于k个可中继端点进行“复制-转发”操作而发生中继冲突的事件.
2 两种通信冲突事件分析2.1 发生事件F的原因分析如图 1所示，虚线正方形区域表示一个传输群，边长为α.每个传输群分为6个区域，分别记为1, 2, …, 6，只有部分小区标识了其所在的区域号. 3，4区域的小区标识在了周围传输群.在区域1的每个小区都存在3个相应的冲突小区(即目标端点所在的小区)，对区域1中的小区z而言为灰色部分小区，而每个冲突小区又有相对应的3个等效干扰端点所处的小区.
|
图 1 传输群示意图 |
相应区域的冲突小区数和对应的干扰节点数如表 1所示. 表 1中，a和b分别为相应区域的冲突小区数和对应的干扰节点数.分隔符区分一个区域中不同小区的a和b数目情况. m表示一个传输群中不同区域的小区数.
|
表 1 传输群中不同区域发生事件F分析 |
小区发生事件F须同时满足以下条件：2个节点所在的小区均为可通信小区；2个节点在可通信小区抢占到通信频谱；目标端点同时位于2个节点的有效传输区域.根据上述3个条件并参照文献[3]引理2的证明得到小区发生事件F的概率为
|
(1) |
式(1) 涉及3个小区，2个小区是发送端所在的小区，1个小区是目标端所在的小区. 2个发送端所在小区被选为可通信小区的概率为
|
(2) |
其中e为发送端点在重叠小区中的情况数.根据表 1，得到
|
(3) |
其中j.m表示区域j在单个传输群中有m个.将相应值代入式(3) 可得
以图 1中区域1的小区z做说明，节点i在小区z获得通信频谱，且可通信范围内只有图中z右侧灰色部分(重叠区域)中存在1个可中继端点r，相应的在带斜线区域中亦存在一个同节点i情况相似的节点j，其也只有r节点可以中继.上述情况即为事件F′2.事件F′相应冲突区域情况及相应小区数如表 2所示. “nodes conflict”表示有2/3/4个节点同时向中继进行“复制-转发”. c为周围传输群小区与该区域小区通信范围相重叠的可能数目；d为周围传输群小区与该区域小区相重叠的小区数为c时的数目；f为这种情况下通信端点数；“-”为该情况不存在.
|
|
表 2 传输群中不同区域发生事件F′分析 |
设定p′(j, k)表示节点i在传输群j区域遇到k个端点发生中继冲突的概率.此情况须同时满足以下条件：① 这k个端点需要同时在各自传输群中取得通信频谱；② 目标端点没有在k个端点的有效传输区域内；③ 只有在k个端点的有效通信区域的重叠区域有可用的中继端点；④ 中继端点数少于k.
除k个冲突端点外的n－(k+1) 个端点可分为以下3类：目标端点、k个冲突端点的公共可用中继端点和其他端点.其中，k个冲突端点的公共可用中继端点数为nr-x，可以存在于网络的任何位置的端点数n1=n－k－nr－x－1；可用中继端点数n2=nr－x－k+1.可用的中继端点指可以中继源端信息的节点，当中继端点已存在源端信息后将转化为非可用中继端点.可用中继端点须在k个端点重叠区域以外，假定有f个.而n3=k-1个潜在中继端点须在重叠区域内.为表述方便，用j.k.f表示区域j有k个端点重叠区域时的可用中继端点数，用j.k.c表示区域j有k个端点重叠区域时的冲突小区数.对于在传输群中的不同区域j和事件F′k(k=2, 3, 4)，发生通信冲突的源端数n′1=k，源端在重叠区域里和外的个数分别为n′2=k－j.k.f和n′3=j.k.f，重叠区域包括的小区数nc=n－(kα2－j.k.c).根据表 2，得到
|
(4) |
其中
|
(5) |
其中：ri, si, ti(i=1, 2, …, k)在数值上等于1，E1(n)=n－n′1，E2(n)=n－nc－n′2，E3(n)=nc－n′3.得到事件F′k(k=2, 3, 4) 的发生概率为
|
(6) |
按照式(4) 计算事件F′k(k=2, 3, 4) 的发生概率难于得到解析解.但可以通过启发式方法得到其数值解.其中，p′(j, k)可以根据表 2取值，如果p′(j, k)不存在于表 2中，则值为0.由表 2可以看出，当k=3, 4时概率值很小，忽略k=3, 4的情况对所求结果影响不大，故仅以k=2的情况代替事件F′，通过化简得到pjk的值为
在单源端单目标端通信时，设源端和目标端成功通信的概率为[3]
|
(7) |
源端成功的传输信息给中继端的概率与中继端成功的中继信息给目标端的概率相等，为[3]
|
(8) |
由式(3)、式(6)、式(7) 和式(8) 得到在网络中发生冲突事件区域端点成功传送信息到目标端和可用中继端点的概率分别为np1－p(F)及np2－p(F′).因为区域6不涉及冲突发生情况，所以可以通过提高区域6中小区成为可通信小区的概率，相应地降低其余区域中小区成为可通信小区的概率的方法减少网络中通信冲突发生数，设定
|
(9) |
其中：p6和p6分别为区域6中小区成为可通信小区的概率和其他区域中小区成为可通信小区的概率，则
|
(10) |
新的传输群调度机制的中继算法如下：
1. if(端点S处在区域6中)
2. 其以
3. else
4. 其以
5. if(端点D在S通信范围内)
6. S与D通信
7. else {
8. if(在S通信范围内存在端点R)
9. S对R执行“发送”操作
10. else
11. S做空操作
12. }
其中：S为源端及可进行“发送”操作的中继端，R为中继端且不包含S要发送的信息，D为目标端，x表示S所在小区可以进行“发送”操作的端点数.
4 仿真设定网络中节点数n为100, 200, …, 900, 1 000，
文献[3]和本文传输群调度机制下，p(F)和p(F′)的理论分析和仿真结果分别如图 2和图 3所示.
|
图 2 事件F的理论和仿真结果 |
|
图 3 事件F′的理论与仿真结果 |
由图 2和图 3可知，改进传输群调度机制后的p(F)和p(F′)的仿真值高于理论值.这是因为发生事件F有以下几种情况：1)2个源端相互冲突；2)1个源端1个中继相冲突；3)2个中继相冲突.但1) 发生的概率最大，为了简化分析问题过程，权以1) 的概率代替.而在计算p(F′)时忽略了当k=3, 4时的概率情况，仅以k=2的情况代替事件F′，所以p(F′)中仿真值亦大于理论值.
传输群调度机制下p(F)和p(F′)值与文献[3]相比均有下降.当网络节点数为900时，发生通信冲突概率的理论值和仿真值和文献[3]相比减小得最小，但也分别减小了26.4%和31.1%.可知，改进后的传输群调度机制可以有效减小网络中通信冲突发生的概率.
5 结束语提出了Ad-Hoc移动网络中多对多场景下的传输群调度机制，根据传输群各个区域在多对多场景下发生事件F和事件F′k(k=2, 3, 4) 的概率不同，来调整相应区域内小区成为可通信小区的概率.理论分析和仿真结果表明，设计的传输群调度机制在多对多场景下能够有效减少通信冲突，提高网络容量.
| [1] | Gupta P, Kumar P R. The capacity of wireless networks[J].IEEE Transactions on Information Theory, 2000, 46(2): 388–404. doi: 10.1109/18.825799 |
| [2] | Grossglauser M, Tse D. Mobility increases the capacity of Ad-Hoc wireless networks[C]//Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM 2001). Anchorage: IEEE, 2001: 1360-1369. |
| [3] | Liu Jiajia, Jiang Xiaohong, Nishiyama H, et al. Delay and capacity in Ad-Hoc mobile networks with f-cast relay algorithms[J].Wireless Communications, 2011, 10(8): 2738–2751. |
| [4] | Liu Jiajia, Jiang Xiaohong, Nishiyama H, et al. Throughput capacity of the group-based two-hop relay algorithm in MANETs[C]//Global Communications Conference (GLOBECOM). Anaheim: IEEE, 2012: 26-30. |
| [5] | Liu Jiajia, Jiang Xiaohong, Nishiyama H, et al. Exact throughput capacity under power control in mobile Ad-Hoc networks[C]//The 31st Annual IEEE International Conference on Computer Communications (INFOCOM 2012). Orlando: IEEE, 2012: 1-9. |
| [6] | Liu Jiajia, Jiang Xiaohong, Nishiyama H, et al. Optimal forwarding games in mobile Ad-Hoc networks with two-hop f-cast relay[J].Selected Areas in Communications, 2012, 30(11): 2169–2179. doi: 10.1109/JSAC.2012.121209 |
| [7] | Wang Xiaofei, Cai Ying, Li Zhuo. Closed-form solution of end-to-end delay with out-of-order delivery in MANETs under random mobility models[J]. 2014, 36(1): 34-40. |
| [8] | Wang Chen, Ye Baoliu, Wang Xiaoliang, et al. Throughput capacity in mobile Ad-Hoc networks with correlated mobility and f-cast relay[C]//Global Communications Conference (GLOBECOM). Anaheim: IEEE, 2012: 702-707. |