多跳无线网中基于空分TDMA的时隙分配策略

韩 成， 吴援明

0 引言

在多跳无线网中一个具有挑战性的问题是如何保证延迟。相关文献研究表明使用CSMA的接入方式，在需提供具有延迟保证的应用环境表现很差[1]。解决这类问题可以引入时分多址接入(TDMA)。但在Ad hoc网络中链路相对较少时使用效率不高。一个对TDMA机制的有效改进方法是空分TDMA，它将无线结点之间的物理距离考虑在内，规定互相不干扰的通讯链路可以在相同的时间片内传输，从而减少了网络所需时间片的总量，从而提高了整个网络的吞吐量。其容量的提高通过时隙的空间复用来实现，而延迟保证有TDMA来提供。

两种基本STDMA调度策略之一是将传输权直接赋予节点。另一种将传输权赋予链路。节点分配算法和链路分配算法在文献[2]中有过深入的探讨。研究表明不论是节点分配还是链路分配在寻找最小长度调度是都归结为全NP问题[3]。在本文中，我们提出了一个结合两者优点的分配策略。该策略基于链路调度，但是传输权被扩展。该方式提高了链路分配的空间利用程度。为了对比该策略是否优于单纯的节点或链路分配，我们使用在TDMA调度中经常使用的网络干扰模型。我们将分别采用分析法和仿真来估计该策略在不同网络连通性下的端到端时延和吞吐量。

1 网络模型

假设使用全向天线并且所有节点具有相同的传输功率。对于任意两个节点(vi, vj)，其中 vi表示发送节点， vj表示接收节点，且 vi≠vj，节点vi和节点vj之间的链路可以成功传输分组的条件是节点间的信噪比(SNR)超过一个门限，即：

其中， Pi表示发送节点 vi的传输功率。 G (i,j)表示节点 vi、vj之间的链路增益。 Nr表示在接收节点所有的噪声功率。如果SNR不小于通信门限γc，我们说一对节点(vi, vj)形成一条链路(i,j)。η表示网络中形成的链路集合，定义为η={(i,j ):Γi,j≥ γc}。任意的链路集合的子集L⊆η，定义发送节点 VT(L) = { vi:(i,j) ∈ L }。

干扰包括背景噪声和所有并发链路的同频干扰。对于任意链路（i, j）∈L，定义干扰如下：

因此，信干噪比 ∏L(i,j)可由以下式子求得：

2 分配策略描述

2.1 链路分配策略

如果{i,j} ∩ { k,l} ≠ Φ ，链路(k,l)称为链路(i,j)的邻近链路。时隙ti对应分配的链路集合为L，由此我们定义Ψ(L)为集合L中各链路对应的邻近链路旁集合。当满足如下两个条件：

时隙it分配的链路集合L中各链路能同时传输。

2.2 节点分配策略

在面向节点的分配策略中，我们定义时隙 ti对应分配的节点集合为V，定义集合V中某一节点v(v∈V)的邻节点为Φ(v)，这里的邻居节点表示能同时接收到节点v传输的分组。设集合V中所有节点的邻节点为Φ(V)，L(V)表示Φ(V)相关的链路集合，为了满足集合V中的节点以及 L (V)中链路能同时传输分组，同样也需要满足如下两个约束：

式(5)表示的物理意义为同时传输的节点不应有相同的邻节点以及同时传输节点的链路相互不应有干扰。

2.3 改进的面向链路分配策略

我们注意到式(3)发生冲突检测的条件依赖于数据包发送节点，而不在于接收节点上。假定某一节点在该时隙中分配为发送节点，这样就存在一条传输链路，如果要更改数据包的传输方向，除了分配的接收节点外，新的接收节点对于不等式(4) ∏l( i,j) ≥γr， ∀( i ,j) ∈ L 仍能得到满足，这就意味着对于其他接收节点的干扰级别并没有改变。

基于上述理由改进的面向链路分配策略可以描述为，对于已分配时隙的链路，首先检查该条链路上是否有分组需要传输，如果没有便将该时隙分配给具有相同发送节点的其他链路(该链路上存在数据包传送)。当然为了避免不必要的分组丢失，无冲突链路可以按照优先级来选择。我们定义该策略为基于扩展传输权限的链路分配策略LET(Link Assignment with Extended Transmission Rights)。

下面我们证明重新分配传输权的链路不会对本时隙中其他链路引入附加的竞争。设按照公式(4)能同时传输的链路集合为L，则 ∏l( i,j) ≥γr，∀( i ,j)∈ L 。打算撤销传输权的链路集合为LR(LR∈L)，该时隙余下的链路集合设为LNR，满足关系 LNR= L LR。重新分配传输权的链路集合为LU，可推得 VT( LU) = VT( LR)。由于 LNR为无冲突链路集合，因此需要证明下式无等式成立：

根据式(4)信干噪比SINR定义可知：

挑战墨西哥和白人文化中根深蒂固的父权价值体系（Madsen,2000:2）是塞利亚文化身份建构的另一关键。

3 分配策略性能分析

本节我们将给出LET性能的一些分析结果。首先讨论吞吐量其次计算在低业务到达率前提下的分组延时。

3.1 分配策略对网络吞吐率的影响

文献[4]中讨论了在固定链路容量和固定路由下的网络吞吐量。文献[5]中提出了链路调度策略的网络最大吞吐量。重写如下：

其中 TL是链路调度的长度。N表示节点的数目，N = V。hij表示在一个调度帧长内，分配给链路(i,j)的时隙数量。Λij表示路由表中包含(i,j)链路的路径数量。对应地，按节点分配的网络最大吞吐量 λN*如下所示：

其中 TN是节点调度的长度， hi表示在一个调度帧长内，分配给节点(i)的时隙数量。Λi表示路由表中包含节点(i)的路径数量。

从以上两式可以看出，如果所有节点或链路都处于饱和状态，那么平均分组时延将会无限长。这时节点吞吐量Λijλ / N (N - 1 )就与 T /hij相等。而且在链路调度中对业务进行完全补偿(hij=Λij)后，上述网络吞吐量的计算可以分别简化为：

这样上式就建立起两种分配方案与吞吐量之间的关系：

所以两种分配方案下的吞吐量与STDMA帧长度相关。

3.2 分配策略对网络延时的影响

转发业务可以使用泊松分布过程来描述。根据网络延时的定义，在面向链路的分配策略中对于广播业务系统网络延时为 dij= TL/2hij其中 dij为链路(i,j)的平均edge delay。

如果对业务进行完全补偿(hij=Λij)后：

这里M为网络中所有链路的总数。

以上两点假设对LET策略同样适用，但由于LET在低业务负载情况下表现为节点分配调度。因此链路分配策略必须扩展到节点，并按照调度中的安排进行广播或单播。因此LET策略的延时可以定义为。进行业务完全补偿后，因此链路分配、节点分配分别与LET之间的时延关系如下：

可见，分配策略时延关系与网络大小、连通度以及调度周期有关。

4 仿真

本节我们评价在不同连接性和节点数下，网络的吞吐量和时延。为了便于比较分别生成了500个节点数量为10、20和40的网络拓扑。每个节点平均产生参数为λ的泊松过程数据流。由于传输功率P不同，将导致拓扑结构连通性的变化。这里定义连通性为单跳内平均每节点的链路数，即M / (N(N - 1 ))。M表示网络中所有链路的数量。

在 20节点高业务负载条件下，链路分配最大吞吐量和节点分配最大吞吐量的比值，根据式(10)应等于TL/TN。仿真结果如图 1所示。从图中可以看出，链路分配策略性能比节点分配策略提供更大的吞吐量，而且不同的网络连通性有不同的吞吐量比，随着连通性的下降链路分配能实现更高的吞吐量。在 20节点低业务负载条件下，我们探讨链路分配平均时延LD与节点分配平均时延ND间的比值关系。从图2可以看出比值基本与连通率呈线性关系。从数值上看，链路分配时延远远大于节点分配时延。并随连通率的增大而增大。

下面我们来探讨节点分配与 LET的关系，如图3为20个节点、低延迟负载条件下， DN/DLET的比值大小。

图 1 吞吐量之比与连通率的关系

图 2 两种分配策略延时比值关系

图3 不同节点数目下吞吐量与连通性的关系

如果参数值大于1则说明LET策略在低负载条件下时比值与连通率的关系，可以看出在不同网络拓扑下该值变化较大，图 4为在 10/20/40节点条件下平均 DN/DLET比值关系。DN/DLET随着连通率的提高而降低，这是由于连通率的提高导致链路分配空分复用能力的降低。并且在中低连了DN/DLET＜ 1 的情况。而网络中节点数越多 DN/DLET比值越大,即LET延迟越小,这是因为网络越大每个节点可供传输的周围节点越多,则LET策略可选的链路也就越多,以致时延减少。

5 结语

从以上三种分配策略分析表明，策略的选择与网络连通率、业务负载和网络大小有关。在高业务负载下，由于链路分配有更高的空间复用能力比节点分配具有更好的吞吐量。相反地，在低业务负载下节点分配能提供节点间更短的传输时间。从仿真结果可以看出，LET策略在保持高吞吐量的前提下，时延比链路分配低很多。而且在中低连通率条件下也比节点分配低。这说明LET策略很好地结合的两者的优点，使性能达到最佳。

[1] Ramanathan S, Lloyd E. Scheduling Algorithms for Multihop Radio Networks[J]. IEEE/ACM Trans. Networking.,1993,1 (02)：166-177.

[2] Nelson R, Kleinrock L.Spatial-TDMA： A Collision-free Multihop Channel Access Protocol[J]. IEEE Trans. Commun., 1985,33(09)：934-944.

[3] Arikan E. Some Complexity Results about Packet Radio Networks[J]. IEEE Trans. Inform. Theory, 1984（IT-30）：910-918.

[4] Asp B,Eriksson G, Holm P. Detvag-90 R_—Final Report,Scientific Report FOA-R-97-00566-504-SE,Defence Research Est., Div. of Command and Control Warfare Tech.[R]. Sweden：[s.n.], 1997.