第２８卷第６期 文章编号：１００６—９３４８（２０１１）０６—００４８—０４ 计算机仿真 ２０１１年６月 卫星网络骨干节点通信冲突算法研究 潘成胜 ，颜伟 ，刘海燕 （１．大连大学信息工程学院，辽宁大连１１６６２２； ２．国家８６３重点实验室，辽宁大连１１６６２２） 摘要：针对卫星网络中骨干节点多对通信中通信所引发的资源冲突问题，为了提高卫星的工作效率与合理分配通信时间，提 出了一种新的解决方法——遗传模拟退火算法（ＧＡＳＡ）。算法克服了遗传算法（ＧＡ）容易陷入局部最优解的缺陷，同时也 解决了模拟退火算法（ＳＡ）收敛速度慢的问题。首先利用ＳＴＫ创建了卫星网络模型，模拟了四颗低轨卫星（ＬＥＯ）向一颗高 轨卫星（ＧＥＯ）通信的场景，然后采用ＯＰＮＥＴ建立通信冲突模型，并对ＧＡＳＡ、ＧＡ和ｓＡ三种算法进行了仿真。仿真结果表 明算法在保证一定吞吐量的前提下，冲突率和延时优于ＧＡ和ｓＡ算法。 关键词：骨干节点；冲突；卫星网络；遗传模拟退火算法 中图分类号：ＴＰ３９１．９ 文献标识码：Ｂ Ｒｅｓｅａｒｃｈ ｏｎ Ｂａｃｋｂｏｎｅ Ｎｏｄｅｓ Ｃｏｍｍｕｎｉｃａｔｉｏｎ Ｃｏｌｌｉｓｉｏｎ Ａｌｇｏｒｉｔｈｍ ｉｎ Ｓａｔｅｌｌｉｔｅ Ｎｅｔｗｏｒｋ ＰＡＮ Ｃｈｅｎｇ—ｓｈｅｎｇ ，ＹＡＮ Ｗｅｉ 一，ＬＩＵ Ｈａｉ—ｙａｎ （１．Ｉｎｆｏｒｍａｔｉｏｎ Ｅｎｇｉｎｅｅｒｉｎｇ Ｃｏｌｌｅｇｅ，Ｄａｌｉａｎ Ｕｎｉｖｅｒｓｉｔｙ，Ｄａｌｉａｎ Ｌｉａｏｎｉｎｇ １ １６６２２，Ｃｈｉｎａ； ２．Ｎａｔｉｏｎａｌ ８６３ Ｋｅｙ Ｌａｂｏｒａｔｏｒｙ，Ｄａｌｉａｎ Ｌｉａｏｎｉｎｇ １ １６６２２，Ｃｈｉｎａ；） ＡＢＳＴＲＡＣＴ：Ｉｎ ｖｉｅｗ ｏｆ ｔｈｅ ｐｒｏｂｌｅｍ ｔｈａｔ ｂａｃｋｂｏｎｅ ｎｏｄｅｓ’ｍａｎｙ—ｔｏ—ｏｎｅ ｃｏｍｍｕｎｉｃａｔｉｏｎ ｉｎ ｓａｔｅｌｌｉｔｅ ｎｅｔｗｏｒｋ ｃａｕｓｅｓ ｔｈｅ ｒｅｓｏｕｒｃｅ ｃｏｎｆｌｉｃｔ，ａ ｎｅｗ ｓｏｌｕｔｉｏｎ，ｔｈｅ ｇｅｎｅｔｉｃ ｓｉｍｕｌａｔｅｄ ａｎｎｅａｌｉｎｇ ａｌｇｏｒｉｔｈｍ（ＧＡＳＡ）ｈａｓ ｂｅｅｎ ｐｒｏｐｏｓｅｄ．Ｔｈｅ ａｌ－ ｇｏｒｉｔｈｍ ｎｏｔ ｏｎｌｙ ｏｖｅｒｃｏｍｅｓ ｔｈｅ ｄｅｆｅｃｔ ｔｈａｔ ｔｈｅ ｇｅｎｅｔｉｃ ｌａｇｏｒｉｔｈｍ（ＧＡ）ｉｓ ｅａｓｉｌｙ ｆａｌｌ ｉｎｔｏ ｔｈｅ ｐａｒｔｉａｌ ｏｐｔｉｍａｌ ｓｏｌｕｔｉｏｎ， ｂｕｔ ａｌｓｏ ｓｏｌｖｅｓ ｔｈｅ ｐｒｏｂｌｅｍ ｔｈａｔ ｈｅｔ ｃｏｎｖｅｒｇｅｎｃｅ ｒａｔｅ ｏｆ ｓｉｍｕｌａｔｅｄ ａｎｎｅａｌｉｎｇ ｌａｇｏｒｉｈｍ（ＳＡ）ｉｔｓ ｓｌｏｗ．Ｆｉｒｓｔ，ｔｈｉｓ ａｒｔｉ— ｃｌｅ ｕｓｅｄ ＳＴＫ ｔｏ ｃｒｅａｔｅ ａ ｓａｔｅｌｌｉｔｅ ｎｅｔｗｏｒｋ ｍｏｄｅｌ ｔｏ ｓｉｍｕｌａｔｅ ｔｈｅ ｓｃｅｎｅ ｉｎ ｗｈｉｃｈ ｔｈｅ ｆｏｕｒ ｌｏｗ—ｅａｒｔｈ—ｏｒｂｉｔ ｓａｔｅｌｌｉｔｅｓ （ＬＥＯ）ｃｏｍｍｕｎｉｃａｔｅ ｔｏ ａ ｈｉｉｇｈ—ｅａｒｔｈ—ｏｒｂｉｔ ｓａｔｅｌｌｉｔｅ（ＧＥＯ），ｔｈｅｎ ｅｓｔａｂｌｉｓｈｅｄ ｃｏｍｍｕｎｉｃａｔｉｏｎ ｃｏｎｆｌｉｃｔ ｍｏｄｅｌ ｔｌｌ ＯＰＮＥＴ，ａｎｄ ｔｈｅ ｔｈｒｅｅ ａｌｇｏｒｉｔｈｍｓ ｏｆ ＧＡＳＡ，ＧＡ ａｎｄ ＳＡ，ｈａｖｅ ｃａｒｒｉｅｄ ｏｎ ｔｈｅ ｓｉｍｕｌａｔｉｏｎ．Ｔｈｅ ｒｅｓｕｌｔｓ ｏｆ ｓｉｍｕｌａｔｉｏｎ ｉｎｄｉｃａｔｅ ｔｈａｔ ｃｏｌｌｉｓｉｏｎ ｒａｔｅ ａｎｄ ｄｅｌａｙ ａｒｅ ｂｅｔｔｅｒ ｔｈａｎ ｔｈｏｓｅ ｕｓｉｎｇ ＧＡ ａｎｄ ＳＡ ａｌｇｏｒｉｔｈｍ ｉｎ ｔｈｅ ｐｒｅｍｉｓｅ ｏｆ ｇｕａｒａｎｔｅｅｉｎｇ ｔｈｅ ｔｈｒｏｕｇｈｐｕｔ． ＫＥＹＷＯＲＤＳ：Ｂａｃｋｂｏｎｅ ｎｏｄｅｓ；Ｃｏｌｉｌｓｉｏｎ；Ｓａｔｅｌｌｉｔｅ ｎｅｔｗｏｒｋ；Ｇｅｎｅｔｉｃ ｓｉｍｕｌａｔｅｄ ａｎｎｅａｌｉｎｇ ａｌｇｏｒｉｔｈｍ（ＧＡＳＡ） 证一定的吞吐量，同时降低多星对一星发生争用冲突的百 １ 引言 随着我国航天事业的发展，卫星网络ＥＩ趋复杂，当有多 分比。 目前对该类问题的研究对象都是关于多个卫星向一个 个骨干节点卫星向一个骨干节点卫星进行通信申请时，由于 地面站通信，本文重点研究骨干节点卫星间的多对一通信。 本算法主要思想是合理的分配卫星的通信时间，这类问题可 采用智能优化算法¨ 火算法进行冲突处理。 被申请的卫星通信资源有限，在接收端会发生冲突，解决这 种冲突的处理方法，对提高航天通信任务的质量和通信设备 的使用效率具有重要意义。在一定的约束和假设条件下，利 用算法处理多对一的冲突问题。具体处理方式采用优先级、 如模拟退火、禁忌搜索（ＴＳ）、遗传 算法和神经网络（ＮＮ）等来求解，本文提出采用遗传模拟退 通信时间和通信质量这三种策略。该问题需要最大限度保 收稿１３期：２０１０—０４—２７ －－－——４８．－－—— 态，即冲突最小和冲突最大的状态（目标值分别为 和 ２遗传模拟退火算法（ＧＡＳＡ） ２．１算法特点 ），并令最差状态相对最优状态的接受概率为Ｐ，，由函数： Ｔ＝（ 一 ）／ｌｎＰ （２） 遗传算法是基于“适者生存”的一种高度并行、随机和自 适应的优化算法 ，它通过复制、交叉和变异等操作，最终 收敛到最适应环境，从而得到问题的最优解或满意解。但是 应用在卫星网络中，遗传算法虽然使卫星在短时间内得到局 部的最优解，但是稍有参数的变动就会全部改变，极不稳定。 可确定初温 ，即模拟退火算法中的初始最高等级数。一般 而言，初温 应选得足够高，才能不使算法很快就落人局部 最优值的陷阱，但又不能选得太高，以减少冗余的迭代。Ｐ， 对应于ＬＥＯ卫星的通信时问选择的接受概率，即初始状态 数据的可信度。 ３．４交叉操作 模拟退火算法能克服上述问题，但是处理时间太长。遗传模 拟退火算法结合了遗传算法和模拟退火算法的特点，使两种 在执行交叉操作前，将整个时间分为Ｋ个时间段，在各 算法的搜索能力得到相互补充，弥补了各自的弱点。 ２．２算法策略 该算法应用于卫星网络的三种策略具体描述如下：一是 按照优先级排序，优先级高的先通信；二是按照通信时长排 序，把卫星的通信冲突时间分配为多个时间段，通信时间长 的先通信；三是按照通信质量排序，有多个卫星同时处于通 信时段，距离短并且文件重要性高的优先通信。 遗传模拟退火算法可以采用第二种策略把它简化为时 间问题，根据可视范围和通信时间为它们分配一个详细的时 间进度表，以及每个时间段应做的工作。假设轨道上有一个 ＧＥＯ卫星。这时有ｎ个ＬＥＯ向ＧＥＯ通信，ＬＥＯ的标号集ｉ＝ １，２，３，…ｎ。每个ＬＥＯ从被发现到不能进行观测的时问弧 段为ｔ 一ｔ ＬＥＯ穿过可视范围的通信时间弧段为ｔ加～ｔ （ｔ ≤ｔ ）。每个ＬＥＯ所需要的最短通信时间为 ，若ＬＥＯ 与ＧＥＯ进行了通信，则通信标志位Ｃ。＝１，否则Ｃ ＝０。从发 现第一个ＬＥＯ开始到最后一个ＬＥＯ脱离ＧＥＯ的通信范围 的总通信时间为ｔ 。算法的时间设为ｔ ，忽略天线的切换时 间及故障等问题。 ３遗传模拟退火算法流程 ３．１编码策略 首先采用编码策略将ＬＥＯ的标号和通信时间绑定，连 成一维数组，奇数位表示标号，偶数位表示通信时间。前者 取值为０到ｎ，后者取值为单位时间的倍数。 ３．２初始分配方式 接着应用启发式方法，当一个ＬＥＯ有多个时间段可供 调整时，任务的调整时间满意度越大，该时间段被选中的概 率越大。定义调整时间满意度函数： Ａｔ）＝ｃｅ蛐 ，Ａｔ＞０ （１） 其中，ｃ．ｄ为正常数， 表示调整后任务的提前或推迟时间。 此函数用来对任务的调整时问进行满意度评估，△ｚ越小，满 意度越大。当 大于任务调整时间上限时，满意度趋于最 小值ｃ。采用启发式方法对一维数组进行操作，随机地产生 初始的时间分配，进而保证一定的质量和多样性，并且启发 式方法的快速性保证了这种算法初始化的速度。 ３．３确定初温 当初始时间分配产生后，算法确定其中的最优和最差状 时间段中按一定的概率随机选择一个时间段与整个时间中 的冲突最小状态以不同的方式进行交叉，直至产生Ｋ个新的 时间段，然后进行替换操作。仿真时采用ＬＯＸ，ＣＩ，ＰＭＸ， ＮＡＢＬＥ这４种不同方式的交叉操作来继承父代优良模 式 ，其中ＬＯＸ能够尽量保留通信时间的相对位置和相对 初始值的绝对位置，ｃＩ能够在不过分打乱通信时间的基础上 提供足够的修改范围，ＰＭＸ能在一定程度上满足模式定理 使最佳通信时间得以最大可能保留，ＮＡＢＬＥ采用置换操作 来快速产生新时间段并使旧时间段发生很大的修改，如此复 合化多交叉操作使得搜索行为具有明显的多样性。交叉概 率的选取通过仿真验证在０．６～０．７时效果最好。 ３．５替换、抽样与变异 采用时间整体替换策略，将作用在不同时间段上的交叉 操作产生的所有新时问段与旧时间段进行整体择优筛选，从 而加速时间分配的寻优过程。 Ｍｅｔｒｏｐｏｌｉｓ抽样过程是针对每个时间段进行的，对旧时 间段采用互换操作（ＳＷＡＰ）产生新时间段，并通过判断函数： Ｔｏ＝ｅ ‘，０≤ ≤１ （３） 来接受新状态 ，式中ｔ为操作的时间点，△为新旧时间段 的目标值差，如此起到概率可控的寻优操作，而且可以做到 增加时间段多样性并避免搜索陷入局部极小。此算法中所 产生的新时间段即变异时间，变异操作的目的是使ＧＡ算法 具有随机搜索能力，并保持群体的多样性。在算法中，变异 概率很小，通常取值为０～０．０２。 ３．６退温操作 最后采用工程中常用的指数退温，即模拟退火算法中的 退温函数： ｔ ＝Ａｔ —ｌ （４） 为退温速率，一般取０．８５～０．９５，退温操作通常能优化时 间的分配。算法的流程图如图１。 ４遗传模拟退火算法的性能分析 必须满足的约束条件有：ＧＥＯ每次只和一个ＬＥＯ通信， 并且和一个ＬＥＯ只通信一次；ＧＥＯ在最短通信时间里执行 通信任务不被打断；当有新的ＬＥＯ出现需要重新执行新的 通信；优先级越高的ＬＥＯ优先保证通信；每个ＬＥＯ都要被通 信到。 ．．．．——４９．．．—— ｆ 利用编码策略产生一维数组 ｉ启发式方法随机产生初始时间分配方式 评价初始时间，确定初温 Ｉ将当前时间分为Ｋ个时间段 １ ｌ 对Ｋ个时间段执行选择和交叉 ｌ 用替换策略得到新时闯段 Ｉ 对Ｋ个时间段执行Ｍｅｔｒｏｐｏｌｉｓ抽样过程 ｌ得到下一代时间分配方式 Ｉ 确定最优时间分配方式 Ｉ申 图１算法流程图 根据算法流程，算法参数选取如下：ＬＥＯ个数取４，时间 段的个数为１００，初温ｌＯ，交叉概率０．６５，变异概率０．０１，退 温速率０．９。算法的计算时间随着ＬＥＯ个数的增加而增大， 只能求得一个估计值ｔ 。 利用ＳＴＫ场景建模，对象包括一个地球同步轨道卫星 ＧＥＯ和四个低轨卫星ＬＥＯ１、ＬＥＯ２、ＬＥＯ３和ＬＥＯ４。该四个 低轨卫星组成一个星座，并同ＧＥＯ形成链路，见表１。 表１卫星对象的参数 卫星可视时间状态图中横轴是时间坐标，纵轴是卫星对 象。横轴被分为１７个时间冲突小段，在图中可以清晰地看 出发生冲突的个数和冲突的时间段，如图２。 ＬＥＯ过ＧＥＯ的数量图反映的是场景时问内每一时刻 ＬＥＯ卫星星座对ＧＥＯ的访问情况。从此图中可以看出图３ 和图２是一一对应的，例如第一小段有四颗卫星，那么就是 说此时ＬＥＯ和ＧＥＯ通信有四颗卫星发生冲突，其他的情况 同上，如图３。 骨干节点多对一ＯＰＮＥＴ仿真图对应于ＳＴＫ软件的场景 建立了四个ＬＥＯ低轨卫星发射节点，一个ＧＥＯ接收节点，首 先建立无线的发射和接收的节点模型，然后建立拓扑结构 图，并导人ＳＴＫ的卫星轨道，收集统计量包括冲突率、延迟和 一５０一 Ｃｈａｉｎ－Ｃｈａｉｎｌ：ＯｂｉｅｃｌＡｃｃｅｓｓ一２２Ｍａｒ２０１０１４．＇２４．＇５９ １ Ｊｕｎ ２０１０ １２：００：００ ０８ＯＪｕｎ ２０１０ １４：００：００肿叭ｒｌ ２０１０ １８：００：Ｏ０ ００Ｏ Ｔｉｍｅ（ＵＴＣＯ） 图２卫星可视时间状况图 Ｃｈａｉｎ．Ｃｈａｉｎｌ：Ｎｕｍｂｅｒ Ｏｆ Ａｃｃｅｓｓｅｓ．２２ Ｍａｒ ２０１０ １４：２４：４６ Ｔｉｍｅ（ＵＴＣＯ） 图３ ＬＥＯ过ＧＥＯ数量图 吞吐量。最后设置仿真时间为４小时，采样点为３６０００个， 如图４。 图４骨干节点多对一ＯＰＮＥＴ仿真图 算法处理后冲突率的时间平均值对比波形图中可以看 出ｓＡ的冲突率为８％左右，ＧＡ的冲突率为６％左右，ＧＡＳＡ 冲突率为３％左右。由图中可以看到ＧＡＳＡ有很强的冲突处 理能力，如图５。 算法延时的时间平均值对比波形图可以看出ＧＡＳＡ延 时最小，１．１８ｓｅｃｏｎｄ左右。其次是ＧＡ，基本稳定在 １．２２ｓｅｃｏｎｄ左右。最后是ＳＡ，大约在１．２５ｓｅｃｏｎｄ左右。由图 中可以看出ＧＡＳＡ的延迟能力要优于其它两种算法，如图６。 ５结束语 遗传模拟退火算法通过统一算法框架将遗传算法和模 拟退火算法两种算法结合，实现优势互补。针对骨干节点多 对一冲突问题采用新的编码策略，有效地提高了算法的寻优 图５ 冲突率的时间平均值对｝Ｅ波形 图６延时的时间平均值对比波形 吞吐量的时间平均值对比波形图中ＧＡＳＡ平均能够达 到３００ｂｉｔ／ｓｅｃ左右。通过比较可以看出ＧＡＳＡ的吞吐量较 低，为了能够降低冲突率的大小，这种算法在保证一定吞吐 量的情况下可以达到冲突处理的目的，如图７。 图７吞吐量的时间平均值对比波形（ｂｉｔｓ／ｓｅｃ） 特性。算法通过建立动态的卫星标号和通信时间来保证算 法的准确性，满足了客观的要求。实验结果表明该算法在卫 星通信网络骨干节点多对一冲突处理方面优于遗传算法和 模拟退火算法。 参考文献： ［１］ Ｅ Ｍｕｔｈｕｒａｍａｌｉｎｇａｍ，Ｓａｎｊａｙ Ｋｕｍａｒ，Ｒ Ｄ Ｖａｓｈｉｓｔｈａ．Ｉｎｆｌｕｅｎｃｅ ｏｆ Ｄａｔａ Ｂｕｒｓｔ Ｃｏｌｌｉｓｉｏｎ ｏｎ ＰＲＢＳ Ｔｒａｎｓｍｉｓｓｉｏｎ Ｔｈｒｏｕｇｈ Ｓａｔｅｌｌｉｔｅ［Ｊ］． ＩＥＥＥ，２００５． ［２］ 范一鸣，余建军，方智敏．融合小生境机制的ＱｏＳ多播路由遗 传模拟退火算法［Ｊ］．通信学报，２００８，２９（５）：６５—７１． ［３］谭伟，赵蔓，李向．基于模拟退火遗传算法的多项目调度问题 研究［Ｊ］．微计算机信息，２００９，２５（３）：２２０—２２２． ［４］ 王军民，李菊芳，谭跃进．有新任务插入的多星动态调度模型 与算法研究［Ｊ］．系统仿真学报，２００９，２１（１２）：３５２２—３５２７． ［５］ 白保存，陈英武．多星任务规划系统调度结构［Ｊ］．计算机工 程，２００８，３４（１５）：２４４—２４６． ［６］ 张娜，柯良军，冯祖仁．一种新的卫星测控资源调度模型及其 求解算法［Ｊ］．宇航学报，２００９，３０（５）：２１４０—２１４５． ［７］ Ｋｉ—ＨｏＬｅｅ，Ｋｙｕ—ＴａｅＪｉｎ，Ｄｏｎｇ—Ｈｏ Ｃｈｏ．Ｒａｄｉｏ Ｌｉｎｋ Ｃｏｎｔｒｏｌ Ｐｒｏｔｏｃｏｌ ｆｏｒ ＷＣＤＭＡ Ｂａｓｅｄ Ｍｏｂｉｌｅ Ｓａｔｅｌｌｉｔｅ Ｃｏｍｍｕｎｉｃａｔｉｏｎ Ｓｙｓ・ ｔｅｍｓ［Ｊ］．ＩＥＥＥ，２００２． ［８］ 祝江汉，黄维．基于协商对策的卫星任务规划冲突消解［Ｊ］．计 算机仿真，２００８，２５（１０）：８６—８９． ［作者简介］ 潘成胜（１９６２一），男（汉族），江苏省无锡市人，博 士，教授，博士研究生导师，主要研究领域为卫星通 信技术，计算机网络技术。 颜伟（１９８５一），男（汉族），山东省莱州市人，硕 士研究生，主要研究领域为卫星通信技术，计算机 网络技术。 刘海燕（１９６３一），女（汉族），黑龙江省萝北市人，博士，教授，硕士 生导师，主要研究领域为卫星通信技术，数字信号处理技术。 一５１—
