ABSTRACT

In this paper, we consider each node in the network as a queuing system. Based on the Geom/G/1 queuing model, we give the average queue length in the buffer of node, and use the Little theorem to get the waiting delay of the packet. By calculating the average overhead of sending a packet, the method of calculating the average utilization of the channel is obtained, and which is applied to obtain the overhead and channel utilization of the Ad Hoc network.

Keywords:Geom/G/1, Ad Hoc, Delay, Channel Utilization

基于Geom/G/1模型的Ad Hoc网络节点性能分析

罗琴，黎锁平，窦祖芳

兰州理工大学理学院，甘肃 兰州

收稿日期：2017年5月10日；录用日期：2017年5月28日；发布日期：2017年5月31日

摘 要

本文将网络中的每一个节点看作一个排队系统，基于Geom/G/1排队模型给出了缓存器中排队分组的平均队长，并利用Little定理得到分组的等待时延。通过计算发送一个分组的平均开销，进而得到了信道的平均利用率的计算方法，并将该方法应用到Ad Hoc网络中，得到了Ad Hoc网络的开销和信道利用率。

关键词 :Geom/G/1，Ad Hoc，时延，信道利用率

Copyright © 2017 by authors and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

1. 引言

Ad Hoc网络是一种特殊的无线移动网络，被广泛应用于无法或不便预先铺设网络设施、或需要快速自动组网的场合等。如军事领域、传感器网络、以及地震、水灾、强热带风暴等自然灾害后的应急通信。Ad Hoc网络是动态网络，具有拓扑结构变化快的特性，对其拓扑结构的刻画、以及传输协议的改进都是非常具有挑战性的问题。为降低问题的复杂度，对于Ad Hoc网络拓扑结构的研究，大多数都停留在单跳，文献 [1] [2] [3] 的研究没有仅仅限于单跳， [1] 是对两跳中继的研究， [2] 和 [3] 则拓展到了对多跳的研究， [2] 侧重于对吞吐量的研究， [3] 侧重于对时延的研究。文献 [4] 对Ad Hoc网络的路由设计做了深入的研究，利用信道增益估计来为设备到用户设置了可靠的发射功率，网络信息以随机接入方式通过路由对报文进行了分发，以帮助建立两台设备之间的单跳或多跳路由。文献 [5] 和 [6] 对两跳多中继协同ARQ和选择重传ARQ (Automatic RepeatreQuest)做了深入研究获得了一系列性能指标。文献 [7] 是用于研究通信业物流的排队论的有用专著，也是我们研究通信系统有效的数学工具。

文献 [8] 计算了QoS和分组传输次数(Packet Delivery Ratio, PDR)等性能指标，较为全面地分析了流量控制协议、资源控制协议、队列辅助协议和优先级感知协议对拥塞检测、拥塞控制和拥塞缓解的影响。文献 [9] 中设计了智能传输控制协议(Intelligent Transmission Control Protocol, iTCP)来进行拥塞控制。文献 [10] 提出了一种有效的跨层自适应传输方法来充分处理移动无线自组织网络中的拥塞。文献 [11] 提出了一种使用具有双无线电接口的快速和慢跳频序列的新型分布式多信道媒体接入控制(MAC)协议，有效提高了网络性能并解决了拥塞问题。这些文献都对网络传输协议做出很好的改进。本文主要通过对网络中每一条链路的性能分析，建立关于每一条链路的数据库，使得Ad Hoc网络在自动组网时，路由选择更加智能化、合理化，从而提高整个网络的利用率，实现拥塞控制。

2. 基于Geom/G/1排队模型的队长分析

Ad hoc作为一种能够快速自动组网的移动网络，每个节点在分组传输过程中都要扮演多重角色，既有可能是源节点、目的节点，也有可能是中继节点，因此一个节点所需要处理的信息量非常大。离散时间排队分析非常适合于节点中等待分组的建模以及数据业务流的分析，是进行计算机系统和通信网络的设计优化与性能分析的有效数学工具。

我们将网络中的节点看作是一个有延迟入口的晚到系统，遵循先到先服务(First In First Out, FIFO)排队规则。分组到达是遵循参数的Bernoulli过程。分组的服务时间独立同分布，其分布、均值和概率母函数分别为

我们只关注发生分组离开系统的时刻，每离开一个分组做一次标记。以表示第个分组离开系统的时刻，是队长过程无后效性的时间点列，称为队长过程的嵌入点。我们用Geom/G/1排队模型来刻画系统中的分组数设第n个分组离去后系统中的分组数。是一个队长过程的嵌入式马尔科夫链，并且有

其中是一个服务期间内到达的分组数，服从二项分布，有分布

的概率母函数是

其中是一个时隙上到达分组数的概率母函数。在一个服务期间内平均到达分组数是

为系统的流通强度或负载，设，表示稳态队长，记。为的转移概率矩阵，无穷维行向量表示离去时刻稳态队长分布。则由平衡方程，可得

该式两端同乘并对求和，有

注意到，解得。使用正规化条件

，

解得，代入得到稳态队长有概率母函数。

稳态下离去时刻系统中的排队分组数是，先求导

求极限，得到系统中排队的平均分组数为

(1)

需要说明的是，此处得到的平均分组数与文献 [7] 中的结论有所不同，可以看作是对其的一个矫正。

3. 基于Little定理的信道利用率

由Little定理我们知道，这里是系统中的分组数，是分组的平均到达率，是分组的平均时延，将上一节中(1)式所得平均队长，及分组平均到达率带入，得到分组的平均等待时延

(2)

如果仅将节点的输出链路作为研究对象，则可根据Little定理得到信道的利用率

(3)

表示在传输链路上的平均分组数，表示分组离开节点进入信道的到达率，表示每个分组在信道上的平均开销。无论是哪条链路，都最多只有一个分组在传输，因此表示信道处于传输状态的时间所占的比例，也就是信道的利用率。

4. Ad Hoc网络性能分析

我们这里研究的Ad Hoc网络采用的是ARQ传输机制。设分组在某条信道上传输的成功率为，最大重传次数为次。为节点发送或接收一个分组所需的开销，为分组传输的路径时延，为发送或接收ACK (acknowledgement)所需的开销，为发送或接收NACK (negative acknowledgement)的开销，设，并且ACK和NACK不会传输错误。如图1是Ad Hoc网络节点分组传输示意图，图中体现的传输过程为节点S向节点D发送了两个分组，第一个分组一次发送成功，第二个分组经历了一次重传才发送成功。节点发送消息时，传输1次便成功的开销为

若传输2次发送成功则开销为，若传输3次发送成功则开销为……，直至传输次发送成功所需要的开销为。传输1次发送成功的概率为，传输2次发送成功的概率为……，传输次发送成功的概率为 ()……，传输次发送成功的概率为。因

图1. Ad Hoc网络分组传输示意图

此，在前次成功发送一帧消息所需的平均开销为。

当第传输失败时，就会进行第次传输。因为对于每一帧消息，节点最多传输次，无论第次发送失败或是成功，这一帧消息都不会再进行下一次传输，第次发送所需的开销为，需要进行第次发送的概率为，所以，当节点要发送一帧消息时，它所消耗的平均开销为

(4)

分组进入某信道的概率可以通过检测获得，并且(4)式所得即为发送一个分组在该信道上的平均开销，将两项指标代入(3)式即可得到该信道的平均利用率。

用这样的方式，我们可以得到Ad Hoc网络中每条链路的利用率，建立数据库，从而帮助Ad Hoc网络在自动组网时优化路由选择，降低拥塞率，提高网络传输性能，使Ad Hoc网络成为更加智能的网络。

5. 结论

本文主要研究了基于Geom/G/1模型的Ad Hoc网络节点性能，首先利用Geom/G/1排队模型分析了节点中的分组队长，并结合Little定理得到了分组在节点中的等待时延，然后对AdHoc网络性能进行了分析，得到了分组传输的开销及信道利用率。

基金项目

本研究受教育部“春晖计划”合作科研项目(Z2016001)资助。

文章引用

罗 琴,黎锁平,窦祖芳. 基于Geom/G/1模型的Ad Hoc网络节点性能分析
Performance Analysis of Ad Hoc Network Node Based on Geom/G/1 Model[J]. 计算机科学与应用, 2017, 07(05): 444-449. http://dx.doi.org/10.12677/CSA.2017.75054

参考文献 (References)