基于多属性决策的空间DTN网络路由算法研究

从立钢，杨华民，王杨惠，底晓强

（1.长春理工大学 计算机科学技术学院，长春 130022；2.长春理工大学 化学与环境工程学院，长春 130022）

空间信息网络在移动通信、导航定位、遥感遥测、深空探索、军事应用等领域所发挥的作用越来越重要，尤其是低轨卫星网络，以其时延短、带宽高、用户终端小、功耗低等优点日益被人们重视，低轨卫星网络已经成为当前信息网络研究领域的热点之一。

低轨卫星网络一般由多颗低轨道卫星组成，其轨道高度为500～2000km之间，一般运行速度为20000km/h，绕地球一周约2小时［6］，由于低轨卫星网络卫星数目较多，且在运行过程中需要频繁切换链路和改变拓扑结构，因此构建可靠、高效的路由机制就变成了一个急需解决的问题。

延迟容忍网络（简称DTN）是针对时延大、中断频繁的特殊网络环境而产生的，因此，其在解决低轨卫星网络路由问题方面具有得天独厚的优势。目前，主流的DTN路由包括以下几种：传染路由（Epidemic Routing）［7］、基于概率的路由（Prophet Routing）算法［8］、散发等待（Spray-and-Wait）路由算法［9］等，以上路由算法应用广泛。但是以上路由算法不能直接应用于卫星网络之中，原因在于其没有考虑卫星网络的自身特点，盲目应用将会影响卫星网络性能的发挥。

本文以低轨卫星网络规律为出发点，针对现有算法存在的适应性问题，提出了一种基于多属性决策理论的低轨卫星DTN网络路由算法，该算法既能解决卫星网络的路由问题，同时对于不同类型的网络任务也具有良好的适应性。

1 网络系统模型

本文所研究的低轨卫星网络采用倾斜轨道，与极地轨道递归卫星星座相比，具有时延小、地面覆盖均匀等优势。

1.1 LEO网络拓扑模型定义

与传统计算机网络不同，低轨卫星网络中的节点是运动的，其拓扑结构是时刻变化的，但是，卫星是严格按照轨道运行的，因此，其变化方式具有明显的周期性和可预测性。基于这一特点，一般进行卫星网络路由研究的时候研究者会利用相关策略屏蔽网络拓扑结构的动态性，利用抽象的静态模型开展研究。目前，相关策略主要有虚拟拓扑策略、虚拟节点策略和覆盖域划分法等，本文采用虚拟拓扑策略。

虚拟拓扑策略是将卫星网络节点的动态拓扑关系离散化，将一个完整的卫星网络运行周期分割为若干时间片［t0，t1］、［t1，t2］、［t2，t3］、［t3，t4］，……，［tn，tn-1］，卫星网络拓扑在时间片内是相对固定的，仅在t1，t2，t3，……，tn等时间节点处发生变化。

1.2 路由问题定义

DTN网络路由的基本模式为“存储-携带-转发”，因此，路由问题可以转化为寻找合适“存储-携带-转发”节点的问题。在低轨卫星网络中，当某一节点产生数据并需要发送给目标节点时，往往会有多条路径可供选择，那么选择路径的第一步就是在多个邻居节点间选择一个合适的节点转发数据，衡量低轨卫星网络通信性能的参数有很多，不同业务对于网络性能也有不同的要求，因此可以将组合参数作为寻找适合数据转发点的重要依据。本文所提出的路由算法正是根据这一想法，利用网络多属性联合决策寻找适合数据转发点，这样既可以完成网络路由任务，同时还能在一定程度上提高网络性能。

2 基于多属性决策的LEO网络路由模型

2.1 多属性决策要素

本算法所选择的属性包括链路带宽（B）、链路建立时延（D）、节点剩余存储空间（S）和节点数据转发率（V）四个。

属性一：链路带宽（B）。星间链路带宽是衡量链路性能的重要属性，低轨卫星网络要进行频繁的数据传输，链路带宽的大小直接影响到网络性能。

属性二：链路建立时延（D）。链路建立时延是指卫星间构建通信链路所耗费的时间，期间要经历天线跟踪瞄准、同步捕获、协议握手三个过程。

属性三：剩余存储空间（S）。本文所研究的低轨卫星网络以DTN为基础，DTN路由的基本模式是“存储-携带-转发”，转发节点的剩余存储空间对于路由过程的顺利实现十分重要，因此将剩余存储空间作为属性之一。

属性四：节点数据转发率（V）。数据节点转发率是指卫星节点转发数据包的数量与其所接收数据包和其自身产生数据包数量之和的比值，该属性是衡量节点数据转发情况的重要参数，通过该属性的引入，可以有效避免在路由过程中“数据黑洞”和“自私”节点的产生。

2.2 决策模型

假设在t时刻，卫星节点s有数据转发需求，此时有n个相邻卫星节点供其选择，作为数据转发节点，即此时为数据源节点s提供了n个数据转发备选方案。每一个方案有m个属性构成的属性集合表示，如A={A1,A2,…，Am}。本文所选择的属性包括链路带宽、链路建立时延、存储空间、网络误码率和节点数据转发率，则属性集可以写成A={B,D,S,V}，根据多属性决策理论，属性值越大对于方案选中越有利的属性被称为效益属性，相反，属性值越小对方案选中越有利的属性被称为成本属性，这五种属性中链路带宽、存储空间、节点数据转发率属于效益属性，链路建立时延和网络误码率是成本属性。

每个备选方案包含四个重要属性，则n个备选方案可以形成一个组成一个n×4的多属性决策矩阵，该决策矩阵形式如下：

各属性含义不同、量纲不同，属性间存在不可公度性，这种差异会在一定程度上最后的决策结果，因此为了提高决策的准确性，可以通过属性标准化的方式来消除数据间的差异。

所研究的属性中同时包括效益属性和成本属性，因此多属性决策矩阵可以通过公式（3）进行规范化，即：

其中，xij为原决策矩阵中的元素，为第j列的最小值，rij为规范化之后的属性值，规范化后的多属性决策矩阵可以表示为R=(rij)n×m。通过公式（2）可以多决策矩阵进行规范化，解决属性间的不可公度问题，方便系统决策。

系统方案评价值的产生不仅需要规范化矩阵，同时还需要属性权重向量的参与，产生方案评价值的公式为：

其中，wj为第j个属性的权重值，权重值需要满足条件。当属性权重确定后，可以通过公式（3）获取路由方案综合评定值，从而完成低轨卫星网络路由节点的选择。

2.3 权重计算

属性权值的选择直接影响到决策的结果，权值的选择应与属性在整个决策过程中所起作用成正比，权重值生成方法的选择会直接影响到最终的评价结果。Echenrode对于权值决策方案进行了分析，并总结了权重计算的经典方法方法［4］，本文采用Shannon所提出的信息熵方法［5］确定决策矩阵权值过。

对于一个决策矩阵D=(xij)n×m，方案对于属性j的评价pij定义为：

将公式（4）的pij带入信息熵计算公式，则方案关于属性j的熵值Ej为：

其中，k是一个常数为，其值为，该值的引入可以确保熵值的范围为［0，1］。信息偏差度dj定义为：

如果在决策过程中没有特殊偏好，即在路由过程中没有特殊业务需求，则可以认为个属性同等重要，因此，此时可以使用类似平均权重的方法生成决策权重，其公式为：

如果在决策过程中对某些属性有特殊偏好，则可以引入偏好值λ对权重进行调整，获得符合实际业务需求的权重，相关计算法方法为：

2.4 路由算法

本文所描述的低轨卫星网络采用虚拟拓扑策略，即认为在每一个时间片内网络结构是相对固定的，在每一个时间片开始时，卫星节点将向其临界点广播当前卫星属性信息，获得广播信息的邻居节点将根据这些信息构建自己的邻节点属性信息表，该表形式如表1所示。当节点有数据需要发送时，就会根据当前的邻节点属性以及任务需求调整属性偏好，进行路由选择。

表1 邻节点属性表

算法具体流程：

（1）当节点有数据传输任务时，判断相邻节点中是否有目标节点，如果有，直接交付数据，路由结束，否则开始步骤（2）；

（2）根据属性信息表计算相邻节点属性权值，根据任务类型，调整属性偏好；

（3）计算方案评价值，选取最优节点进行数据转发；

（4）目标节点收到数据后重复步骤（1）。

需要注意的是，本算法中步骤（2）（3）中参与权值计算的节点不包括之前已经完成方案价值计算的节点，这样的设计可以有效避免“路由环路”的出现。

3 算法分析及仿真

假设一个的低轨卫星网络通信场景，场景中包括卫星节点vs、v1、v2、v3、v4、v5、v6、vd，卫星网络拓扑关系及相关属性如表2所示，其中为vs数据源节点，其所要发送的数据量为100M，vd为目的节点，假设在［t1，t2］时间段内路由过程可以完成。

表2 邻节点属性表

3.1 路由算法分析

（1）无偏好路由选择

当路由选择无业务偏好时，假设节点的剩余空间均满足数据要求，将上文所述的场景使用多属性决策路由算法进行路由选择。经过计算，此时选择的路径为vs--＞v2--＞v5--＞vd。

（2）偏好网络时延

如果当前的业务对于特定属性要求较高，可以通过引入偏好值来引入属性偏好值来改变路由策略，从而提高网络在该方面的性能，更好的支持当前业务。链路网络时延较高，可以在路由选择过程中引入对时延有利的偏好值λ对权重进行调整，在进行路由选择过程中会对路径进行重新调整，这里设置偏好值λ=（0.1，0.6，0.1，0.1，0.1），此时选择的路径为vs--＞v2--＞v6--＞vd。，与无偏好情况相比，路径发生了改变，这里用链路建立时间较短的节点v6替换了节点v5，在兼顾网络其他性能的同时最大程度的降低了网络整体时延。

3.2 性能仿真分析

本文利用DTN仿真软件ONE，结合以上场景对算法进行仿真，并将无偏好路由算法、时延偏好路由算法、Epidemic以及PROPHET四种路由算法进行对比，以验证其性能。

如图1所示，在四种路由算法中，Epidemic路由算法的传输成功率最低，无偏好的路由算法的成功率明显高于Epidemic和PROPHET路由算法，而转发率偏好路由算法的传输成功率又高于无偏好多属性路由算法。

图1 网络传输成功率

如图2所示，说明了三种路由算法在假定场景下的平均时延情况，可见对于同一任务，多属性路由算法的平均时延均低于Epidemic和PROPHET路由算法，而时延偏好多属性路由算法的平均网络实验又略低于无偏好多属性路由算法。

图2 网络平均时延

通过以上仿真结果分析，可见多属性决策路由算法的性能要明显优于常见的Epidemic路由算法，而且当业务对于某一属性有特殊需求时，使用偏好多属性决策路由算法又会在相关属性上有进一步提高。

4 结论

本文提出了一种基于多属性决策理论的空间DTN网络路由算法，通过选择链路带宽、链路建立时延、节点剩余存储空间、误码率、节点数据转发率五种重要属性作为决策基础，引入多属性决策理论构建路由模型，该算法可以针对不同业务需求对路由算法进行动态调整。仿真结果表明：该算法与Epidemic、PROPHET两种路由算法相比较，在性能上确实有一定提高，而且能够按照业务偏好提高相关性能，为空间网络不同业务需求提供灵活可靠的网络路由服务。