日盲紫外非视距Ad-hoc通信网络共享信道优化方法

摘要

本发明公开了日盲紫外非视距Ad-hoc通信网络共享信道优化方法，首先根据日盲紫外非视距Ad-hoc网络特点画出三种通信模式下的冲突图，提出冲突避免模型；然后，基于冲突避免模型构造链路冲突图，并提出将染色理论用于日盲紫外非视距Ad-hoc网络共享信道的时隙分配控制方法上，并进一步提出适用于日盲紫外非视距Ad-hoc网络的UVAd-TDMA协议。本发明提供的方法得到的局部链路冲突图的点色数较少，亦即对单位时间划分的时隙数较少，实现了日盲紫外非视距Ad-hoc通信网络在单位时间内用最少时隙数为相互冲突的链路分配不同的互补干扰信道的目的。

说明书

技术领域

本发明涉及日盲紫外非视距Ad-hoc通信网络共享信道优化方法。

背景技术

日盲区域紫外光通信是通过大气散射进行信息传输的一种通信方式，具有非视距 NLOS(Non—Line—of—Sight)传输、保密性好、抗干扰能力强、建造和维护成本低等优点。 上述优点使得日盲区域紫外光通信可作为射频通信一种很好的替代方式而广泛地应用于 乡村、城市室外环境以及军事通信的环境中。但由于近地大气分子和微粒对日盲紫外光的 强吸收作用，使得其传输距离受到了限制。

无线Ad-hoc网络是一种临时无中心的分布式网络，它的节点可以任意移动，各节点 的地位是平等的。源节点可以通过多跳到达目的节点。而日盲紫外非视距Ad-hoc通信网 络可结合紫外光通信非视距传输、抗干扰能力强、保密性好的优点及Ad-hoc网络的多跳 性，来实现可靠的远距离的传输，弥补了日盲紫外光非视距通信系统通信距离短的缺陷。 可见，日盲紫外非视距Ad-hoc通信网络是满足各类移动场景通信要求的新型有效手段。

日盲紫外光非视距通信有三种方式：全向发全向收方式，其特点是：定位要求最低、 无限的散射体积、最小的带宽；定向发全向收方式，其特点为：在散射体积内具有最大的 紫外光能量、有限的散射体积、比较大的带宽；定向发定向收方式，其特点为：有限的散 射体积、最大的带宽。相应的，组建紫外光网络，其节点间的相邻关系可按通信方式分为 全向——全向邻居、全向——定向邻居、定向——定向邻居等情形。因此，类似于传统射 频通信网络使用定向天线所产生的问题，日盲紫外非视距Ad-hoc通信网络采用定向光束 在实际通信中争用信道资源时将会产生聋节点、增益不对称、暴露终端和新隐藏终端等问 题。

日盲紫外非视距Ad-hoc通信网络节点共享信道时存在的问题，实际上都是由于定向光 束的方向性及在全向或定向光束覆盖范围内存在多个紫外光节点传输业务产生冲突造成 的。因此，在一个具有n个紫外光节点的日盲紫外非视距Ad-hoc网络系统中，由于定向光 束的方向性及其中数据流的时空竞争特性，使得处于聋区域的节点无法通信，以及相互干 扰区域的源节点或目的节点在同时发送或接收数据时将产生时间上和空间上的冲突，从而 造成能够同时成功传输数据的源节点——目的节点对是有限的。为使得在单位时间内成功 传输数据的源节点——目的节点对数目最多，即日盲紫外非视距Ad-hoc通信网络中可并发 链路最多，就需要对有限的紫外光信道资源进行传输调度。这就是共享紫外光信道的时空 优化分配问题。

发明内容

针对现有技术存在的上述问题，本发明要解决的技术问题是：如何通过日盲紫外非视 距Ad-hoc通信网络节点共享信道时空优化分配，使得日盲紫外Ad-hoc通信网络达到较好 的通信效果。

为实现上述发明目的，本发明采用如下技术方案：日盲紫外非视距Ad-hoc通信网络

共享信道优化方法，包括如下步骤：

步骤1：建立了日盲紫外非视距Ad-hoc通信网络三种信道模式下的冲突避免模型：

S11：全向——全向通信方式的冲突避免模型如式（1）：

|N1-N2|≥(1+Δ)(r₁+r₂)  （1）；

其中，Δ>0，表示保护带区域，N1和N2均表示日盲紫外非视距Ad-hoc通信网络的节 点，r₁和r₂分别表示节点N1，N2在全向数据传输时的有效传输距离；

S12：全向——定向通信方式下的冲突避免模型如式（2）：

|N1-N2|≥(1+Δ)(r₁'+r₂)  （2）；

其中，Δ>0，表示保护带区域，N1和N2均表示日盲紫外非视距Ad-hoc通信网络的节 点，r₁'表示节点N1在定向数据传输时的有效传输距离，r₂表示节点N2在全向数据传输 时的有效传输距离；

S13：定向——定向通信方式下的冲突避免模型如式（3）：

|N1-N2|≥(1+Δ)(r₁'+r₂')  （3）；

其中，Δ>0，表示保护带区域，N1和N2均表示日盲紫外非视距Ad-hoc通信网络的节 点，r₁'表示节点N1在定向数据传输时的有效传输距离，r₂'表示节点N2在定向数据传 输时的有效传输距离；

步骤2:构建日盲紫外非视距Ad-hoc通信网络的局部链路冲突图，具体步骤如下：

S21：构造链路干扰近似模型：

每条链路仅和自身的ξ跳内的邻居链路存在干扰，其中 R=min{r_i,r_i'}表示节点的传输半径，R'=max{r_i,r_i'}表示节点的干扰半径；

S22：利用日盲紫外非视距Ad-hoc通信网络中节点的计算能力计算，各节点产生包含 有自己业务传输及所受干扰信息的广播数据包，用全向光束将该广播数据包发送给其ξ跳 内的邻居链路节点；

S23：每个节点都保存它的ξ跳内节点发送的广播包，并生成日盲紫外非视距Ad-hoc 通信网络的局部链路冲突图；

步骤3：根据步骤2建立的日盲紫外非视距Ad-hoc通信网络的局部链路冲突图计算最 优染色序列，具体如下：

S31：设步骤2建立的日盲紫外非视距Ad-hoc通信网络的局部链路冲突图为 M_λ,c=(Λ,l_λ,c)，该局部链路冲突图的μ—点染色是从局部链路冲突图M_λ,c=(Λ,l_λ,c)的顶点 集Λ到色数集PC(μ)的一个映射σ；当且仅当λ_i,λ_j∈Λ，且λ_iλ_j∈l_λ,c时，σ(λ_i)≠σ(λ_j)， 局部链路冲突图M_λ,c=(Λ,l_λ,c)的μ—点染色集合记为Ξ_μ(M_λ,c)，若|Ξ_μ(M_λ,c)|≠0，则称 局部链路冲突图M_λ,c=(Λ,l_λ,c)是μ—点可染色的，其中，λ_i，λ_j分别表示链路冲突图 M_λ,c=(Λ,l_λ,c)的顶点集Λ中的第i个和第j个顶点，l_λ,c表示冲突链路集，σ(λ_i)表示λ_i的 染色值，σ(λ_j)表示λ_j的染色值，色数集PC(μ)表示染色值构成的集合；

S32：采用遗传算法与贪心算法相结合进行链路冲突图的染色，具体步骤如下：

S321：构建染色体空间：

用A(M_λ,c)=(ai_j)_k×k表示局部链路冲突图M_λ,c=(Λ,l_λ,c)的邻接矩阵，具体如式（4）：

$a_{\mathrm{ij}}\left(\begin{array}{ccc}1& \mathrm{if}& {\lambda }_i{\lambda }_j\in l_{\lambda ,c}\\ 0& \mathrm{if}& {\lambda }_i{\lambda }_j\notin l_{\lambda ,c}\end{array}\right)---\left(4\right);$

其中k表示链路冲突图M_λ,c=(Λ,l_λ,c)的阶数，a_ij表示邻接矩阵A(M_λ,c)=(ai_j)_k×k中的元 素，对局部链路冲突图M_λ,c=(Λ,l_λ,c)顶点的所有染色方案构成染色体空间；

对染色体空间作如下编码：

设M_λ,c=(Λ,l_λ,c)的k个顶点的一种顺序为n₁，n₂...n_k，其中n₁，n₂...n_k是自然数的 {1,2,...,k}的一种排列，对应于一个长度为k的序列x₁x₂...x_i...x_k，其中x_i表示对 M_λ,c=(Λ,l_λ,c)的顶点λ_i所着的颜色，x_i∈PC(μ)；

对染色体空间进行编码后，利用贪心算法产生由整数组成的N条染色体组成的初始种 群，则对应于一个长度为k的序列x₁x₂...x_i...x_k成为一条染色体x，x_i则成为该条染色体的 第i个基因；

S322：设定适应度函数：

定义罚函数如式（5）:

$p\left(x\right)=\underset{i=1.j=i+1}{\overset{k}{\Sigma }}\eta ({\lambda }_i,{\lambda }_j)---\left(5\right);$

且

η(x)表示染色体空间中染色体x违反约束的边的数目；

定义适应度函数如式（7）：

$\rho (x_1{x}_2...x_k)=\frac{1}{p\left(x\right)+|\chi \left(x\right)-ϵ-1|}---\left(7\right);$

其中χ(x)是染色体x=(x₁x₂...x_k)中所用的颜色数,ε为已求得的μ—点可染色方案中所 用的颜色最小值；

S333：遗传选择概率γ_i的确定：

对于适应度值为ρ_i的第i条染色体x，它的遗传选择概率γ_i可用公式（8）计算：

${\gamma }_i=\frac{{\rho }_i}{\underset{j=1}{\overset{\mathrm{pop}\_\mathrm{size}}{\Sigma }}{\rho }_j}---\left(8\right);$

其中求和上限pop_size的取值是种群规模N；

S324：交叉算法的确定：

设x=(x₁x₂..x_i..x_k)和z=(z₁z₂...z_i...z_k)是参加交叉的两个父代染色体，依次对基因 x_i,(i=1,2,...,k)和z_i,(i=1,2,...,k)分如下两类情况交叉：

1）当基因x_i<ε和z_i<ε时,若使得(λ_i,λ_j)∈l_λ,c,x_i=x_j，则令x_i=z_i；

2）否则，令x_i=min(x_i,z_i)；

S325：变异算法的确定：

在染色体x=(x₁x₂...x_k)中随机选择两个位置,对这两个位置之间的基因值进行重新排 序,其它位置的基因保持原来的值不变；

S326：逆转算法的确定：

在染色体x=(x₁x₂...x_k)中随机选取两个位置,然后将这两个位置之间的基因值逆转；

S327：遗传算法的终止条件：

每一代种群的平均适应度值可通过（9）计算:

$\bar{\rho }=\frac{\underset{j=1}{\overset{\mathrm{pop}\_\mathrm{size}}{\Sigma }}{\rho }_j}{N}---\left(9\right);$

遗传算法的终止条件为0<θ<1；

步骤4：求解表示局部链路冲突图最优染色的染色序列，具体步骤如下：

输入：局部链路冲突图M_λ,c=(Λ,l_λ,c)，邻接矩阵A(M_λ,c)=(ai_j)_k×k；

输出：表示局部链路冲突图最优染色的染色序列；

Step1群体初始化,设置控制参数，群体规模为N,最大进化代数为gen,交叉概率为γ_c,变异 概率为_γm；

Step2贪心算法:

使用整数字符串编码方式，采用贪心算法得到N个局部次优解，使群体初始化，具体 贪心算法如下：

A1如果局部链路冲突图M_λ,c=(Λ,l_λ,c)中还有未染色顶点，执行步骤A2，否则贪心 算法结束，执行遗传算法；

A2从任一极大团Q内任一顶点出发，寻找与它拓扑距离最短另一极大团P的顶点， 染相同的颜色T，以组成可以并发的链路集合；

A3继续寻找与步骤A2中的极大团Q拓扑距离最短且和该极大团Q中所有顶点都不 相连的顶点，对该顶点染与步骤A2中相同的颜色T，并添加进可以并发的链路集 合；

A4重复步骤A3，如果无法再找到符合条件的顶点添加进可以并发的链路集合，执 行步骤A5；

A5从局部链路冲突图M_λ,c=(Λ,l_λ,c)中删去前述已染色顶点以及与前述顶点相连的 边，再执行步骤A1；

Step3遗传算法：

B1gen=0，生成初始种群Pop(0)，初始种群Pop(0)中有N条染色体；

B2利用适应度函数（7）计算gen代种群中N条染色体的适应度值；

B3若满足算法遗传算法的终止条件,则输出满足算法终止条件的染色体，该染色体 上的基因序列即为表示局部链路冲突图最优染色的染色序列；否则执行B4；

B4采用式（8）确定的遗传选择概率γ_i复制初始种群中的N条染色体得到新的N条 染色体；

B5对新的N条染色体按照交叉概率γ_c成对选择N_c条染色体，应用步骤S234确定的 交叉算法在成对的两条染色之间进行交叉；再按照变异概率γ_m选择N_r条染色 体，应用步骤S325确定的变异算法进行变异；然后再随机选择的N_n条染色体， 应用步骤S326中的逆转算法进行逆转，得到下一代种群，设gen=gen+1，返回B3；

步骤5：基于步骤4得到表示局部链路冲突图最优染色的染色序列建立日盲紫外非视距 Ad-hoc通信网络的非竞争MAC协议，具体如下：

将日盲紫外非视距Ad-hoc通信网络中染相同颜色的节点分配在同一时隙，染不同颜色 的节点分配在不同时隙，时隙的个数等于随染色数；

在所述非竞争MAC协议中，若干个时隙组成一帧，每一帧分为控制子帧和数据子帧， 每一帧的开始是控制子帧，利用控制子帧将各节点传输业务分配到数据子帧中各数据时 隙，处于冲突域范围内的所有节点共享控制子帧的调度及数据时隙分配信息。

相对于现有技术，本发明具有如下优点：

1、针对实时构造的局部链路冲突图对其染色，适用于日盲紫外非视距Ad-hoc通信网 络的动态分布式特点，可满足网络拓扑时变的要求。

2、贪心算法结合遗传算法对局部链路冲突图染色，能够快速得到近似最优染色结果， 因而适用于拓扑动态变化的日盲紫外非视距Ad-hoc通信网络的共享无线信道分配。

3、基于本发明提供的方法得到的局部链路冲突图的点色数较少，亦即对单位时间划分 的时隙数较少，同时也满足了日盲紫外非视距Ad-hoc通信网络在单位时间内用最少时隙 数为相互冲突的链路分配不同的互不干扰信道的目标。

4、目前尚无针对日盲紫外非视距Ad-hoc通信网络提出冲突避免的MAC协议，本发明 首次提出适用于日盲紫外非视距Ad-hoc通信网络的冲突避免MAC协议——UVAd-TDMA 协议。国内外均未见相关报道。

附图说明

图1为全向——全向通信方式下的冲突模型。

图2为全向——定向通信方式下的冲突模型。

图3为定向——定向通信方式的冲突模型。

图4为一个日盲紫外非视距Ad-hoc通信网络拓扑图。

图5a为图4对应的链路冲突图，图5b为图5a对应的极大团。

图6a为链路冲突图的最优染色，图6b为基于图6a中链路冲突图的时隙划分。

图7a为10个节点的链路冲突图，图7b为图7a中链路冲突图的染色效果图。

图8a为16个节点的链路冲突图，图8b为图8a中链路冲突图的染色效果图。

图9a为21个节点的链路冲突图，图9b为图9a中链路冲突图的染色效果图。

图10为UVAd-TDMA协议下的帧结构。

图11为各节点时隙分配及时隙结构图。

图12为UVAd-TDMA协议与IEEE802.11系统吞吐量比较。

图13为UVAd-TDMA协议与IEEE802.11端到端延迟比较。

具体实施方式

下面结合附图和实施例对本发明的技术做进一步详细说明。

日盲紫外非视距Ad-hoc通信网络共享信道优化方法，包括如下步骤：

步骤1：建立了日盲紫外非视距Ad-hoc通信网络三种信道模式下的冲突避免模型：

S11：全向——全向通信方式的冲突避免模型如式（1）：

|N1-N2|≥(1+Δ)(r₁+r₂) （1）；

其中，Δ>0，表示保护带区域，保护带区域可由实际网络确定，N1和N2均表示日盲 紫外非视距Ad-hoc通信网络的节点，r₁和r₂分别表示节点N1，N2在全向数据传输时的有 效传输距离。

参见图1，节点N1和节点A通信，节点N2和节点B通信，则冲突区域为以节点N1全 向数据传输时的有效传输距离r₁为半径所画圆和以节点N2全向数据传输时的有效传输距 离r₂为半径所画圆的公共部分。为了避免冲突，节点N1和N2之间的距离至少应该为 (1+Δ)(r₁+r₂)，其中Δ>0是保护带区域，以避免相邻节点在相同紫外光信道上的同时传输； 自然，冲突区域可被定义为发送者能覆盖的区域，故|N1-N2|≥(1+Δ)(r₁+r₂)为可避免冲 突的最短距离。即全向——全向通信方式的冲突避免模型如式（1）：

|N1-N2|≥(1+Δ)(r₁+r₂)  （1）。

S12：全向——定向通信方式下的冲突避免模型如式（2）：

|N1-N2|≥(1+Δ)(r₁'+r₂) （2）；

其中，Δ>0，表示保护带区域，N1和N2均表示日盲紫外非视距Ad-hoc通信网络的节 点，r₁'表示节点N1在定向数据传输时的有效传输距离，r₂表示节点N2在全向数据传输 时的有效传输距离。

参见图2，节点N1和节点A通信，节点N2和节点B通信，冲突区域可用式（a）表示：

S_CDEF≈S_扇N1CD-S_ΔN1EF   （a）；

|N1-N2|≥(1+Δ)(r₁'+r₂)为可避免冲突的最短距离。全向——定向通信方式下的冲突 避免模型如式（2）：

|N1-N2|≥(1+Δ)(r₁'+r₂)  （2）。

S13：定向——定向通信方式下的冲突避免模型如式（3）：

|N1-N2|≥(1+Δ)(r₁'+r₂')  （3）；

其中，Δ>0，表示保护带区域，N1和N2均表示日盲紫外非视距Ad-hoc通信网络的节 点，r₁'表示节点N1在定向数据传输时的有效传输距离，r₂'表示节点N2在定向数据传 输时的有效传输距离。

参见图3，节点N1和节点A通信，节点N2和节点B通信，干扰区域为不规则图形 CDEF，|N1-N2|≥(1+Δ)(r₁'+r₂')为可避免冲突的最短距离。定向——定向通信方式下的 冲突避免模型如式（3）：

|N1-N2|≥(1+Δ)(r₁'+r₂')  （3）。

步骤2:构建日盲紫外非视距Ad-hoc通信网络的局部链路冲突图，具体步骤如下：

S21：构造链路干扰近似模型：

每条链路仅和自身的ξ跳内的邻居链路存在干扰，其中 R=min{r_i,r_i'}表示节点的传输半径，R'=max{r_i,r_i'}表示节点的干扰半径；

S22：利用日盲紫外非视距Ad-hoc通信网络中节点的计算能力计算，各节点产生包含 有自己业务传输及所受干扰信息的广播数据包，用全向光束将该广播数据包发送给其ξ跳 内的邻居链路节点；

S23：每个节点都保存它的ξ跳内节点发送的广播包，并生成日盲紫外非视距Ad-hoc 通信网络的局部链路冲突图。由于ξ跳外的链路与其不存在干扰，所以生成该局部链路冲 突图以对其信道分配已足够。局部链路冲突图反映了日盲紫外非视距Ad-hoc网络中所有 数据流的冲突关系。

如果一条日盲紫外非视距Ad-hoc通信网络链路上数据流的发送端或接收端在另外一 条链路上流量的发送端或接收端的传输范围内，且两个发送端或接收端同时发送或接收数 据，则这两条日盲紫外非视距Ad-hoc通信网络链路称为冲突链路。冲突链路上的数据流 不能同时并发。

冲突图(CI，collision image)，是指在三种冲突避免模型的约束下链路的冲突图，即由 第l_i条链路及受第l_i条链路传输影响的其他日盲紫外非视距Ad-hoc通信网络链路的集合。 本发明对中局部链路冲突图M_λ,c=(Λ,l_λ,c)，其中Λ={λ₁,λ₂,...,λ_k}是日盲紫外非视距Ad-hoc通 信网络中所有源节点发送的数据流集合，边λ_iλ_j∈l_λ,c当且仅当数据流λ_i和λ_j冲突。

显然，链路冲突图是无向简单图。链路冲突图中顶点表示日盲紫外非视距Ad-hoc通信 网络中的链路，若链路间存在干扰，则在链路冲突图的相应顶点间连一条边。链路冲突图 表示了日盲紫外非视距Ad-hoc通信网络中所有链路之间可能存在的冲突情况。

经典图论中，图的顶点染色规则是：相邻的顶点着色不同；链路冲突图模型的链路调 度规则是：相邻顶点不能同时并发。由此可见，链路冲突图的调度规则与图染色规则是相 同的，着色相同的点表示所对应的日盲紫外非视距Ad-hoc通信链路可以同时处于工作状 态，着色不同的顶点表示相对应的日盲紫外非视距Ad-hoc通信链路不能同时处于工作状 态。在日盲紫外非视距Ad-hoc通信网络中将时间分成等长的工作时隙，着色相同的点所 对应的日盲紫外非视距Ad-hoc通信链路可以工作在一个时隙中，即一种颜色对应紫外光 通信TDMA调度中的一个时隙。为了最大化网络吞吐量，在确保完成所需的通信任务的前 提下，应最小化整个网络的通信调度周期。因此，要求日盲紫外非视距Ad-hoc通信TDMA 调度算法应该用最少时隙数完成其网络中业务的传输。因此，求得日盲紫外非视距Ad-hoc 通信网络资源调度的最小时隙数等价于用最少色数为链路冲突图染色。这样日盲紫外非视 距Ad-hoc通信网络媒体接入控制的信道资源调度问题巧妙地转换为链路冲突图的顶点染 色问题。

如图4是一个具有7个节点的日盲紫外非视距Ad-hoc通信网络拓扑图，设源节点1发送 数据流量λ₁与源节点3发送数据流量λ₃时存在冲突，源节点4发送数据流量λ₄和源节点5发 送数据流量λ₅时存在冲突，则图4相应的链路冲突图如图5所示。

在经典图论中，若在某一简单无向图的子图中任意两个顶点都相邻，则称该子图为原 图的团。但如果在该子图中任意增加新顶点后，它就不再成为团，则称该子图为原图的极 大团。在一个图中，顶点数目最多的极大团称为最大团。显然，处于链路冲突图同一个团 中的各顶点(对应日盲紫外非视距Ad-hoc通信网络拓扑中的链路)不能同时传输数据，不同 时属于任何一个团的顶点间可以无冲突地并发数据。

如图5所示，图5a是一个链路冲突图，图5b显示该链路冲突图中包含了2个极大团，处 于同一极大团内的各链路由于空间上的相互冲突而不能够同时发送或接收数据。

本发明首先对日盲紫外非视距Ad-hoc通信网络局部链路冲突图进行顶点染色，寻求其 点色数；然后根据点色数值，将某一单位时间长度划分为等长的时隙，相同颜色的顶点所 对应的紫外光链路可以工作在一个时隙中，即一种颜色对应日盲紫外非视距Ad-hoc通信网 络工作节点调度中的一个时隙，如图6所示。图6a中，使用2种颜色实现了链路冲突图的最 优染色，等价于图6b中使用2个时隙完成网络中业务的传输。

由于日盲紫外非视距Ad-hoc通信网络是一个分布式的网络系统，若在这样一个分布式 系统中采用集中式方法构造链路冲突图，首先必须要将整个日盲紫外非视距Ad-hoc通信网 络的拓扑信息和业务要求信息都汇聚到一个计算能力强大的节点，以产生完整的链路冲突 图，然后由一个计算中心处理器进行计算，最后将结果(调度方案)分发到每个日盲紫外非 视距Ad-hoc通信网络节点，显然这在日盲紫外非视距Ad-hoc通信网络中是不可能实现。在 真实的日盲紫外非视距Ad-hoc通信网络场景中，实用的链路冲突图构造方法应该是并行、 分布式的，只依赖局部信息，可以在较短的时间内，获得一个接近最优的链路冲突图。

步骤3：根据步骤2建立的日盲紫外非视距Ad-hoc通信网络的局部链路冲突图计算最 优染色序列，具体如下：

S31：设步骤2建立的日盲紫外非视距Ad-hoc通信网络的局部链路冲突图为 M_λ,c=(Λ,l_λ,c)，该局部链路冲突图的μ—点染色是从局部链路冲突图M_λ,c=(Λ,l_λ,c)的顶点 集Λ到色数集PC(μ)的一个映射σ；当且仅当λ_i,λ_j∈Λ，且λ_iλ_j∈l_λ,c时，σ(λ_i)≠σ(λ_j)， 局部链路冲突图M_λ,c=(Λ,l_λ,c)的μ—点染色集合记为Ξ_μ(M_λ,c)，若|Ξ_μ(M_λ,c)|≠0，则称 局部链路冲突图M_λ,c=(Λ,l_λ,c)是μ—点可染色的，其中，λ_i，λ_j分别表示链路冲突图 M_λ,c=(Λ,l_λ,c)的顶点集Λ中的第i个和第j个顶点，l_λ,c表示冲突链路集，σ(λ_i)表示λ_i的 染色值，σ(λ_j)表示λ_j的染色值，色数集PC(μ)表示染色值构成的集合。

不失一般性，将日盲紫外非视距Ad-hoc通信网络的工作时间设定为单位时间，单位 时间可以为一天24小时，也可为1个小时，可根据实际需要而设定。

S32：采用遗传算法与贪心算法相结合进行链路冲突图的染色，具体步骤如下：

S321：构建染色体空间：

用A(M_λ,c)=(ai_j)_k×k表示局部链路冲突图M_λ,c=(Λ,l_λ,c)的邻接矩阵，具体如式（4）：

$a_{\mathrm{ij}}\left(\begin{array}{ccc}1& \mathrm{if}& {\lambda }_i{\lambda }_j\in l_{\lambda ,c}\\ 0& \mathrm{if}& {\lambda }_i{\lambda }_j\notin l_{\lambda ,c}\end{array}\right)---\left(4\right);$

其中k表示链路冲突图M_λ,c=(Λ,l_λ,c)的阶数，a_ij表示邻接矩阵A(M_λ,c)=(ai_j)_k×k中的元 素，对局部链路冲突图M_λ,c=(Λ,l_λ,c)顶点的所有染色方案构成染色体空间；

对染色体空间作如下编码：

设M_λ,c=(Λ,l_λ,c)的k个顶点的一种顺序为n₁，n₂...n_k，其中n₁，n₂...n_k是自然数的 {1,2,...,k}的一种排列，对应于一个长度为k的序列x₁x₂...x_i...x_k，其中x_i表示对 M_λ,c=(Λ,l_λ,c)的顶点λ_i所着的颜色，x_i∈PC(μ)；如编码序列124...μ表示序号n₁所对应图 M_λ,c=(Λ,l_λ,c)的顶点λ₁着颜色1，序号n₂所对应图M_λ,c=(Λ,l_λ,c)的顶点λ₂着颜色2，序号n₃所对应图M_λ,c=(Λ,l_λ,c)的顶点λ₃着颜色4，…，序号n_k所对应图M_λ,c=(Λ,l_λ,c)的顶点λ_k着 颜色μ。

对染色体空间进行编码后，利用贪心算法产生由整数组成的N条染色体组成的初始种 群，则对应于一个长度为k的序列x₁x₂...x_i...x_k成为一条染色体x，xi则成为该条染色体的 第i个基因；

S322：设定适应度函数：

定义罚函数如式（5）:

$p\left(x\right)=\underset{i=1.j=i+1}{\overset{k}{\Sigma }}\eta ({\lambda }_i,{\lambda }_j)---\left(5\right);$

且

η(x)表示染色体空间中染色体x违反约束的边（即有冲突的边）的数目；

定义适应度函数如式（7）：

$\rho (x_1{x}_2...x_k)=\frac{1}{p\left(x\right)+|\chi \left(x\right)-ϵ-1|}---\left(7\right);$

其中χ(x)是染色体x=(x₁x₂...x_k)中所用的颜色数,ε为已求得的μ—点可染色方案中所 用的颜色最小值；

S333：遗传选择概率γ_i的遗传算子的选择确定：

遗传选择概率γ_i采用轮盘赌选择，即适应度高的染色体被选择的机会大。对于适应度 值为ρ_i的第i条染色体x，它的遗传选择概率γ_i可用公式（8）计算:

${\gamma }_i=\frac{{\rho }_i}{\underset{j=1}{\overset{\mathrm{pop}\_\mathrm{size}}{\Sigma }}{\rho }_j}---\left(8\right);$

其中求和上限pop_size的取值是种群规模N；

S324：交叉算法的确定：

设x=(x₁x₂..x_i..x_k)和z=(z₁z₂...z_i...z_k)是参加交叉的两个父代个体,依次对基因 x_i,(i=1,2,...,k)和z_i,(i=1,2,...,k)分如下两类情况交叉：

1）当基因x_i<ε和z_i<ε时,若使得(λ_i,λ_j)∈l_λ,c,x_i=x_j，则令x_i=z_i；

2）否则，令x_i=min(x_i,z_i)；

上述交叉算法，1）的交叉方式可以减少遗传算法的盲目搜索，2）的交叉方式，使得 个体所用的颜色数逐渐减少，将问题的搜索空间缩小。在上述交叉算法的作用下，有效的 顶点分割信息得到保留，又会产生一些新的个体。交叉算法可以减少交叉后代所用的颜色 μ,(μ≥ε),而适应度函数又可以保证所用颜色为(ε-1)种的染色体以较大概率存活到下一 代种群中。

S325：变异算法的确定：

在染色体x=(x₁x₂...x_k)中随机选择两个位置,对这两个位置之间的基因值进行重新排 序,其它位置的基因保持原来的值不变；例如：

父亲:323|123|465

儿子:323|123|645

S326：逆转算法的确定：

在染色体x=(x₁x₂...x_k)中随机选取两个位置,然后将这两个位置之间的基因值逆转；例 如:

父亲:323|123|465

儿子:323|321|465

上述变异算法和逆转算法有利于保持种群的多样性,可以有效的使算法不致陷入局部 最优。

S327：遗传算法的终止条件：

每一代种群的平均适应度值可通过（9）计算:

$\bar{\rho }=\frac{\underset{j=1}{\overset{\mathrm{pop}\_\mathrm{size}}{\Sigma }}{\rho }_j}{N}---\left(9\right);$

遗传算法的终止条件为0<θ<1；

步骤4：求解表示局部链路冲突图最优染色的染色序列，具体步骤如下：

输入：局部链路冲突图M_λ,c=(Λ,l_λ,c)，邻接矩阵A(M_λ,c)=(ai_j)_k×k；

输出：表示局部链路冲突图最优染色的染色序列；

Step1群体初始化,设置控制参数，群体规模为N,最大进化代数为gen,交叉概率为γ_c,变异 概率为γ_m；

Step2贪心算法:

使用整数字符串编码方式，采用贪心算法得到N个局部次优解，使群体初始化，具体 贪心算法如下：

A1如果局部链路冲突图M_λ,c=(Λ,l_λ,c)中还有未染色顶点，执行步骤A2，否则贪心 算法结束，执行遗传算法；

A2从任一极大团Q内任一顶点出发，寻找与它拓扑距离最短另一极大团P的顶点， 染相同的颜色T，以组成可以并发的链路集合；

A3继续寻找与步骤A2中的极大团Q拓扑距离最短且和该极大团Q中所有顶点都不 相连的顶点，对该顶点染与步骤A2中相同的颜色T，并添加进可以并发的链路集 合；

A4重复步骤A3，如果无法再找到符合条件的顶点添加进可以并发的链路集合，执 行步骤A5；

A5从局部链路冲突图M_λ,c=(Λ,l_λ,c)中删去前述已染色顶点以及与前述顶点相连的 边，再执行步骤A1；

Step3遗传算法：

B1gen=0，生成初始种群Pop(0)，初始种群Pop(0)中有N条染色体；

B2利用适应度函数（7）计算gen代种群中N条染色体的适应度值；

B3若满足算法遗传算法的终止条件,则输出满足算法终止条件的染色体，该染色体 上的基因序列即为表示局部链路冲突图最优染色的染色序列；否则执行B4；

B4采用式（8）确定的遗传选择概率γ_i复制初始种群中的N条染色体得到新的N条 染色体；

B5对新的N条染色体按照交叉概率γ_c成对选择N_c条染色体，应用步骤S234确定的 交叉算法进行交叉（即选择了多对染色体，在每对染色体之间的两条染色体之间 采用交叉算法进行交叉）；再按照变异概率γ_m选择N_r条染色体，应用步骤S325 确定的变异算法进行变异（即对选择的每条染色体分别采用变异算法进行变异）； 然后再随机选择的N_n条染色体，应用步骤S326中的逆转算子算法对种群中随机 选择的N_n条染色体进行逆转（即对选择的每条染色体分别采用逆转算法进行逆 转），得到下一代种群，设gen=gen+1，返回B3；

步骤5：基于步骤4得到表示局部链路冲突图最优染色的染色序列建立日盲紫外非视距 Ad-hoc通信网络的非竞争MAC协议，具体如下：

将日盲紫外非视距Ad-hoc通信网络中染相同颜色的节点分配在同一时隙，染不同颜色 的节点分配在不同时隙，时隙的个数等于染色数；

在所述非竞争MAC协议中，若干个时隙组成一帧，帧结构如图10所示，每一帧分为 控制子帧和数据子帧，每一帧的开始是控制子帧，利用控制子帧将各节点传输业务分配到 数据子帧中各数据时隙，处于冲突域范围内的所有节点共享控制子帧的调度及数据时隙分 配信息。

数据子帧中的时隙，各节点根据控制子帧中协同调度表中规定的时隙收发数据。在每 个数据时隙，可同时有多对节点进行收发。数据子帧由多个数据时隙构成，各节点根据控 制子帧的协同调度进行数据时隙的分配，在每个数据时隙，可同时有多对节点进行收发数 据。

参见图11，数据时隙分别被分配给一个或多个节点发送或接收数据。每个数据时隙由 前保护时段、转发时段、数据接收/分发时段与后保护时段组成。转发时段用于转发从其它 节点接收的、需要全局共享的信息，数据接收/分发时段用于接收邻居节点传输的信息或分 发本地产生的信息。

为增强日盲紫外非视距Ad-hoc通信网络的实用性，必须考虑在其应用尤其是军事应 用中，网络中各节点产生的某些信息需要扩散至全网，供所有节点共享。日盲紫外非视距 Ad-hoc通信网络中的定向光束虽然具有更大的网络吞吐量，然而相比于全向光束，为了将 某个节点的信息扩散至全网却需要花费长的多时间。实际上，很多军事信息在传播过程中 都具有时效性，传播时间过长，将导致目的节点最终接收到的军事信息失效。为此，在 UVAd-TDMA协议中，采取了捎带转发的方式，即在每个时隙的转发时段（见图11）捎带 转发已收到的其它节点需要全网共享的“本地信息”，实现全局共享信息的高效广播。

实施例1：在Pentium(R)Dual-Core CPU,E52002.50GHz1.21GHz，2.00GB的硬件环 境下，对具有10个节点，16个节点，21个节点的链路冲突图进行染色，得到如下结果：

由图7、图8、图9及表1可以看出，对10个节点的链路冲突图的最优染色只用了2 种颜色，21个节点仅用了3种颜色，而对16个节点的链路冲突图的最优染色也却用了4 种颜色，这是因为16个节点的链路冲突图的边与顶点的关系比21个节点的链路冲突图的 边与顶点的关系复杂，因此所用色数相对增多。但在运行时间上，16个节点用了48.59420s， 21个节点用了98.9220s，其所耗费时间主要用在群体初始化时的贪心算法运行上。

表1

链路冲突图节点数 色数 代数 运行时间（s） 10 2 2 1.375020 16 4 6 48.59402 21 3 7 98.92200

实施例2：采用NS2模拟场景为10个节点随机分布在1000m*1000m的区域内,节点的 发送范围为200米，节点运动假定为随机游动。模拟的主要参数如表2所示。

表2

参数 值 节点数 10 仿真范围 1000m×1000m 数据包大小 216bit 模拟时间 1000s 物理层速率 1028b/s 节点运动最大速度 20m/s

图12比较了UVAd-TDMA协议与IEEE802.11的系统吞吐量。在相同负载下， UVAd-TDMA协议的系统吞吐量比IEEE802.11有明显的提高,提高原因是UVAd-TDMA协 议利用共享信道最优分配算法及紫外有向光束增加了时隙的重用,提高了信道利用率。

图13比较了UVAd-TDMA协议与IEEE802.11的端到端延迟。在相同负载下由于IEEE 802.11的竞争特性使其具有较低延迟,而UVAd-TDMA协议由于运行共享信道最优分配算 法呈现较高延迟，但仍在网络传输可接受范围（<0.000055s）。

最后说明的是，以上实施例仅用以说明本发明的技术方案而非限制，尽管参照较佳实施例 对本发明进行了详细说明，本邻域的普通技术人员应当理解，可以对本发明的技术方案进 行修改或者等同替换，而不脱离本发明技术方案的宗旨和范围，其均应涵盖在本发明的权 利要求范围当中。