文摘

探讨一种新颖的联合路由问题,调度和信道分配single-radio多通道无线网状网络中多个通道宽度可以通过一个新的软件技术动态调整,这样更多的并发传输和抑制重叠通道可以实现干扰。虽然以前作品研究了这个关节的问题,问题的线性规划模型并不包含一些微妙的约束。因此,本文首先构造一个线性规划模型更加实际的问题,然后提出了一种模拟退火方法新颖的编码机制,多个时段的配置设计描述动态传输过程。实验结果表明,我们的方法可以找到相同或相似的较小规模的最优解问题的解决方案,可以有效地找到高质量的各种大规模问题的解决方案。

1。介绍

无线网状网络(WMNs)能够实现更高的网络覆盖率和一个更大的传输范围通过大规模部署的节点和节点之间的数据交换。除了传统的无线网络功能,WMNs可以动态地访问网格路由器,设置,和调试;也就是说,即使一个网格路由器关闭,网络本身可以执行自动复位和发现。一般来说,路由的实际问题,调度,和信道分配WMNs是难以计算的,,因此,很多启发式和metaheuristic算法提出了有效地解决相关的问题,例如,蚂蚁路由问题的模拟退火算法(1),链接的近似动态规划方法调度(2),基于本地搜索的节能空间调度算法(3),信道分配问题的遗传算法部分重叠的通道(4),等等。

除了个别问题路由、调度、信道分配WMNs, metaheuristic算法WMNs关节问题的进行了调查;例如,解决了联合路由和调度问题的遗传算法(5];解决了联合路由和信道分配问题的模拟退火算法(6)和遗传算法(7),等等。然而,大多数以前的联合问题WMNs只有两三个相关问题,因此本文进一步探讨联合路由问题,调度,信道分配(RSC)来解决网络场景更实际。WMNs另一个重要的问题是信号干扰的影响网络性能,可减少通过使用多个无线电和多个正交通道;例如,参见[8,9]。最近工作(10]提出了一种软件技术非常小的开销,可以动态地适应多个通道的宽度在不同的时间,以获得更多的并发传输,减少信号干扰下有限的无线频谱资源。注意,尽管以前作品的联合RSC问题[11,12)提出了这样的不同宽度的信道分配方案应用于控制信号干扰,一些微妙的约束并不关心他们的线性规划模型。

鉴于上述情况,本文首先构造一个线性规划模型,更好地反映WMNs联合RSC的问题,然后设计了模拟退火(SA)算法和一种新的编码机制来解决这个问题。我们的方法试图更实际地解决WMN如何运作和快速确定可行的路径和时间表,以及不同宽度的数据传输信道分配的大规模网络拓扑。此外,我们进一步将干扰信号在信道容量的影响考虑在内,以更好地反映真实网络的情况。我们的实验结果是第一个与小规模问题的最优解,不考虑干扰信号在信道容量的影响,然后进行综合实验分析更复杂的问题。注意,在工作11)提出了一个SA方法联合路由、链路调度,和频谱分配,但其线性规划模型和SA的方法和我们不同。

本文的主要贡献表示如下:(我)SA算法,设计并实现了一种新型编码机制来解决小说联合RSC问题不同宽度的信道分配方案;(2)我们建立一个线性规划模型的小说联合RSC的问题,为了更真实的比之前的作品(11,12),我们认为通道容量被分配信道宽度的影响,传播范围,和信号干扰;(3)我们提出一个创新的解决方案编码设计的配置多个时段设计描述WMNs动态数据传输过程。

本文的其余部分组织如下。部分2涵盖了文献综述和信道分配方案。部分3给我们SA算法的解决方案编码设计有关的问题,然后描述了算法的细节。部分4三角裤的设计实验方案及其结果。部分5本文总结与未来工作。

2。预赛

本节首先提供相关文献评论,然后描述了不同宽度的信道分配方案,最后介绍了公式在信号干扰。

2.1。相关工作

WMN无线多次反射技术,使用中的所有网络设备作为中继节点传输范围。基于WMN的路由机制,可以从源节点传送数据,中继节点的路由路径,最后到目标节点。如图1,所有的设备在WMN分为网格路由器(或先生)或网客户端(MC)。除了它的基本的路由功能,在网络先生也作为传输数据到互联网网关和桥梁。会话是传播MCs和夫人之间利用P2P机制作为临时指定的模式。MC,对其硬件和软件的支持远远比一个先生,更容易因为MC不作为网关和桥梁。因此,它只需要一个无线适配器和交通负载处理的协议比的轻先生在流动性方面,一个奥比MC静止。MC,夫人是网的骨干网络。

大多数之前的与本文相关的工作都致力于改善整个网络的吞吐量和发展新方法来解决路由问题,调度和信道分配。路由问题是关心确定最优路径进行数据传输;例如,李et al。13)提出了一个自适应路由算法对多个用户WMNs;斯考特et al。8)应用累积期望传输时间加权的方法来评估是否多通道分配方法可以有效地提高网络吞吐量。调度问题主要是关于数据传输的优先级和序列;例如,唐et al。14)建造了一个模型,可以适当安排,最大化输出效率和功率控制和应用一种算法基于时间序列理论解决所有相关问题。信道分配问题是关心信号干扰和并发传输,和一个适当的分配有限的频谱资源可以最大化传输效率;例如,Ko et al。15)开发了一种模块化分布式信道分配方法,使渠道选择决策基于获得的信息从数据转发机制。

随着越来越多的研究分别针对这三个问题,一些作品开始讨论如何共同组成的两个或三个个人问题可以马上改进。例如,联合路由和调度问题,十二月et al。5)建立了一个整数线性规划模型,提出了一种遗传算法方法联合路由和调度问题。李等人。16)提出了一个优化体系WMNs联合多路径路由和调度,而罗et al。17)将贪婪算法和列生成算法能够有效地提高整个网络的吞吐量。联合路由和信道分配问题,Raniwala et al。18,19使用当地的交通信息,整合与分布式和集中式算法,以处理动态信道分配和路由搜索。程和杨6)提出了一个模拟退火算法基于面向路径的编码机制,利用树的数据结构来表达每个候选解多个路径。Valarmathi和Malmurugan20.)设计了一个traffic-aware和预测机制来控制路由拥塞和使用分布式信道分配,以避免信号干扰在同一个频道。

更复杂的问题,一些作品集中在联合路由问题,调度,信道分配问题(RSC)。例如,唐宋Brandt-Pearce [21)使用自由空间光学通信,无线频谱技术,以抵消频谱资源不足,使用了一个混合整数规划的方法来解决两个无线技术的联合RSC问题。Uddin et al。11,12)采用了不同宽度的信道分配方案构造联合RSC模型,解决了列生成算法和启发式。

2.2。不同宽度的信道分配

信道分配是一个重要的主题研究IEEE 802.11 MAC协议。一个好的信道分配方法可以大大减少并发传输的干扰,提高吞吐量,减少传输延迟(15]。多种渠道的使用可能会增加信道分配的复杂性,但可以进一步减少信号干扰的影响网络性能。单通道和多通道分配之间的区别(22)如图2在节点1和2传输会话节点3和4,分别。在单通道分配下,两个链接分配频道1,节点1和2可以在传输过程中相互干扰。在这种情况下,应设置两个交易日传输优先级。另一方面,在多通道分配下,节点2和4之间的联系可以分配到另一个频道,与不同的目标节点可以同时传输,信道容量是只在一个通道信号干扰的影响。

通过软件设置,夫人,以及MCs,不同宽度的信道分配方案可以采用10]。除了标准20 MHz通道宽度的分配,不同的通道宽度(包括5 MHz, 10 MHz, 20 MHz,和40 MHz)为多个频道可以根据传输范围以及传输的会话数。因此,在工作10)量化传输通道宽度的影响范围和传输会话的数量,以及功耗,并发现一个较小的通道宽度更适合一个链接以更少的交通负荷,因为如果一个小通道宽度是分配,剩余的频谱带宽可以用来创造更多的正交其他并发传输渠道。

工作(23)已经为不同宽度的信道分配问题,提出了一个模型表明,不同宽度的信道分配方案可以使一个更公平和更有效地利用有限的频谱资源和明显表现优于传统的固定宽度的信道分配方案。工作(24)提出了一个算法来抑制干扰并发传输和使用不同宽度的信道分配方案增加正交通道的数量。根据工作(24),不同宽度的信道分配方案可以提高整个网络的吞吐量。

2.3。信号干扰

考虑两个相邻节点之间的传输和他们之间的欧氏距离。假设没有干扰和一个简单的2-ray传播模型,打算接收机的信噪比(信噪比)和派生的传输范围分别给出如下: 在哪里传动功率;路径损耗指数;是热噪声的功率谱密度;是分配通道宽度;和所需的阈值信噪比必须达到一个特定的数据速率。从上面的方程,一个更大的传输范围可以实现与较小的通道宽度。如果链接的交通负载较重,一个更大的通道宽度应该分配给该链接。

考虑从其他传输干扰的存在,在接收机signal-to-interference-plus-noise比(SINR)香农容量的链接分别给出如下: 在哪里所需的阈值,必须不少于SINR实现一个特定的数据率。从上面的方程,可以实现一个更大的信道容量如果一个更大的通道宽度分配。

3所示。我们的SA RSC的问题的方法

本部分首先描述了我们有关WMNs RSC问题,建立一个线性规划模型的问题,和封面的设计SA算法,包括解决方案编码机制,生成最初的解决方案,和搜索周边的解决方案。

3.1。问题描述和建模

考虑传输并发会话的- node多次反射WMN与正交通道,每个会话从传输节点到节点和它的交通负荷位为;分配每个通道的光谱带5、10、20或40 MHz在不同的时间;也就是说,它是一种变长信道分配方案。传播参与联合路由问题,调度,和信道分配每个会话都可以被分成子沿着不同的路径到达目的地,这些路由路径选择根据底层安排不同的并发传输。我们的问题的目标是最小化总系统激活时间传输并发会话时的最小SINR传输满足要求。

因为不同的通道宽度可能会影响传输范围,只有两个相邻节点传输范围内(由分配通道宽度),在不违反最低SINR需求可以相互通信。的链接两个相邻节点可以互相交流被称为一个活跃的链接。注意,活动链接在不同时期是不同的。让表示所有可能的活动链接的集合。例如,在图3两个交易日,大小和传输9-node网络拓扑;所有的活动链接是由虚线表示;节点和(黑色)是会话的源和目的节点1,而节点和(灰色)是会话的源和目的节点2。

不同宽度的信道分配方案,本文继续使用总频谱宽度的设置(11,12]:= 80 MHz。有别于传统的宽度固定信道分配方案,分配20 MHz为传输所有的链接,本文采用四个可能的渠道宽度:5、10、20和40 MHz,如图4。如果通道宽度的链接分配更小、传播范围更大,有更多的正交通道可以被使用,但通道容量小。相反,如果分配通道宽度的链接比较大,传播范围更小,而且有更少的剩余可用频谱资源分配,但通道容量大。

接下来,我们关心的问题的线性规划模型描述的细节。我们假设一个时分多路访问WMN,时间分为次槽。注意,每个链接是活跃的和需要分配一个通道宽度只有当传输范围约束并不违反和SINR要求是满意。因此,多次反射传输通过活动链接在每个时间段可能需要不同的时间;也就是说,任何两个时段的时间可能不相等。为,让表示的持续时间th时间段,这被称为系统激活时间。我们关心的问题的目标是最小化总系统激活时间如下:

假设有正交通道,可以分配在一个时间段。通过使用不同宽度的信道分配方案,总频谱宽度(80 MHz)至少可以切成2通道宽度40 MHz和16通道的宽度5 MHz,,因此,。让表示一个特定的频道。变量的联系定义如下:

假设每个节点分配与single-radio通道;即,每个链接在一个时间段不允许任何交通流从这个链接的两个方向同时分配只有一个通道。因此,传输约束在每个时间段的特点如下: 在哪里表示节点在网络拓扑结构的集合。

频谱带宽分配给信道在时间槽给出如下: 因为所有的总额正交通道在时间槽不能超过总频谱宽度的约束特点是如下: 如果,然后没有频谱带宽分配渠道在时间槽;也就是说,必须等于0。因此,我们有以下约束: 链接变量和通道宽度变量,分配通道宽度和链接的活动状态在时间槽由如下: 线性化的定义为减轻计算的数学模型,三大积极的常数,,,这个模型,用于构造:

从信噪比方程(1),因为分配通道宽度决定了最大传输距离,我们需要约束:如果两个节点之间的距离超过这个范围,会议不能成功地传播。从上面的推导,链接分配和通道宽度吗,所以传输范围由(1),因此,我们有以下约束: 线性化上面的不平等,我们有以下: 在哪里是一个很大的积极的常数。

每个活动链接在每个时间段,如果SINR(例如,)大于阈值,信道容量不受影响;否则,信道容量下降。线性化SINR方程 在哪里是一个很大的积极的常数。让表示时间段的香农容量可以由以下约束: 注意,上面的不平等可以线性化。

假设会话的数量吗流经链接流约束特征如下: 方程(17)执行有关,如果节点源节点和目标节点,每个会话吗流入节点最终必须出来。方程(18)和(19)执行的总流出源节点和目标节点的总流入会话必须。

让会话的数量流经链接在时间段。也就是说, 因此,th系统激活时间可以计算如下:

以下约束执行总交通负载流经链接不得超过该链接可以维持的最大容量: 下面的一些变量非负约束执行:

总而言之,我们的线性规划模型的目标是最小化总系统激活时间(3one-time-slot传输约束(下),5),通道宽度约束(7)- (12),传播范围约束(14),SINR约束(15),香农容量约束(16),一次交通流量约束(17)- (19),系统激活时间约束(20.)- (21),一个链接交通流量约束(22)和非零变量约束(23)。

值得一提的是,我们的模型之间的差异和RSC问题提出了(前面的模型11,12]介绍(14)- (16)和(20.)- (21)。详细的解释说明如下:(我)不同于以前的工作,不平等(14)考虑分配通道宽度对传输的影响范围。它要求两个节点之间的传输范围由于分配通道宽度不少于他们的欧氏距离;(2)以前的工作没有考虑SINR的线性规划模型。在本文中,(15)认为,不同的活动链接和他们不同的传输范围导致不同的SINRs;(3)以前的工作只考虑的总通道容量约束传播。摘要信号干扰信道容量的影响被认为是在为每个链接(14)- (16),因此,每个链接在每个时间段的信道容量可能不同;(iv)在此基础上,不同的能力导致不同的系统激活时间为每个时间段。因此,本文介绍了(20.)- (21)计算系统激活时间为每个时间段。

3.2。我们的SA算法

SA算法(23,25)是一个迭代的改进过程启发从模拟退火过程和经常被用来解决各种组合优化的问题,例如,零售分销系统的周期性路由问题[26)和动态设施布局问题(27),等等。SA的基本思想是模拟退火过程的金属晶体迭代优化解决方案的质量和寻找接近最优解。首先,任何解决有关问题的编码定义为系统状态的金属,和之间的关系有关问题的目标函数和能量函数的状态是指定。接下来,SA算法初始化初始系统状态以及一些参数对温度。在SA算法的每次迭代中,系统温度降低到一个固定的水平显示退火调度和邻近国家当前的系统状态在当前系统产生的温度。如果这个邻国的能级状态(更好的)低于当前状态,周边国家取代当前状态;否则,允许相邻的国家有一个接受概率更高(更糟糕的)能级来取代当前状态。一旦当前状态稳定在当前的温度,我们重复相同的退火过程,直到当前温度低于最低温度。接受概率机制,系统可以释放陷阱不断寻求更好的局部最优解,因此能找到全局最优解的有关问题。

SA算法的流程图如图5。SA算法的主要步骤说明如下:(我)设置最高温度最低的温度,当前的温度;(2)生成初始状态并评估其能量;(3)改变当前状态通过扰动生成一个新的状态,并评估其能量。状态也被称为邻近的国家吗;(iv)计算能量差国家间的和。如果,即相邻的状态较低能级,然后国家吗替换当前状态。否则,生成一个随机数并计算接受概率,在那里玻耳兹曼常数,通常设置为1,是当前系统温度。如果,那么相邻的状态接受替换当前系统状态;否则,它被拒绝;(v)如果最大数量迭代是没有达到在当前温度,我们回到步骤(3);(vi)如果,当前的温度根据退火计划却降低了,在那里,然后我们回到步骤(iii);时,算法停止。

鉴于上述情况,我们需要设计系统状态的能量函数和算法的一些主要组件专门为我们关心的问题。由于本文是关注一个最小化问题和SA还解决了最小能量水平,我们可以直接使用(3)作为系统状态的能量函数。因此,剩余的组件,我们必须设计包括状态编码机制,生成初始状态的方法,和我们的邻居搜索方法,该方法在本节的其余部分详细。

3.2.1之上。国家编码

与SA算法来解决我们的问题,我们需要设计一种机制来编码的解决有关问题变成一个系统状态。对于我们的问题,信息系统的状态需要的网络拓扑节点的数目,每个会话的大小,下一跳的会话传输和目标节点,以及分配通道宽度。由于时间分为多个时间段,我们第一次编码时间槽的配置如图6(a),其中包括以下五个属性:(我)节点:这个记录的ID节点在网络拓扑结构;(2)队列1 - 3:因为我们允许最多三个交易日呆在同一个节点在一个时间点,我们假设每个节点有一个队列和三个条目标记为“队列1”-“队列3。“每个条目的队列可以存储一个会话保持在当前节点,记录它的规模和它的价值。如果该值为0,这意味着队列条目是空的;(3)目的地1 - 3:“目的地“入境记录会话的目标节点的ID”队列“当前节点的;(iv)下一跳:这记录的ID下一跳节点的会话在“队列1”传播。如果下一跳节点的ID是与“目的地1”,然后传输会话的“队列1”将在这个时间段完成;(v)通道宽度:这记录分配通道宽度的链接从当前节点的下一跳;例如,一个20 MHz通道宽度是分配给链接(1,6)图6(一)。

保证解的可行性,一个时间段的配置需要满足以下约束条件:(我)每个节点的队列是先进先出,因此,,如果“队列”条目是0,那么“队列+ 1”条目必须是0;(2)如果所有节点的队列条目都是0(意味着没有会话在节点),然后“下一跳,”“目的地”和“通道宽度”条目必须为该节点0;(3)如果一个节点的“下一个跃点”输入为0(这意味着没有会话传播从这个节点),然后“通道宽度”必须;(iv)因为有限的通道宽度和信号干扰,一些会话可能滞留在当前时间槽。例如,在图6(一),“下一个跃点”和“通道宽度”条目在节点为1.72 mbit会话3都是0,而且,因此,此会话保持在当前时间节点3槽和只会传播后时段;(v)在同一时间段,分配通道宽度的总和”通道宽度不能超过总频谱带宽,也就是说,80 MHz,。

把图6(a)作为一个例子为传播的六个交易日6-node网络拓扑:两个交易日在节点1和一个会话在每个节点2 - 5。图6(b)的编码配置完图的时间空档6(一)解释如下:(我)假设所有分配通道宽度在图6(一)足以允许每个会话的传播;(2)尺寸3.58 mbit节点的会话1图6(一)消失在图6(b)因为目的地ID是一样的下一跳的ID数字6(一);也就是说,它到达目的地后这时间段;(3)会话的大小4.71 mbit的队列2节点1移动到“队列1”,并相应地调整相应的目的地;(iv)没有行动的会议规模1.72 mbit节点3因为没有分配给相邻节点的联系通道宽度3;(v)三个交易日(尺寸1.13,6.55,和0.71 mbit, resp)。在图6(一)有相同的下一跳节点(节点3)。然而,节点3(即只有两个空队列条目。队列,队列2”和“3”)。在这种情况下,我们任意选择两三个交易日的传播。在这个例子中(见图6(b)),大小6.55和0.71 mbit的会话到达节点3,而会话大小1.13 mbit呆在原节点2。

一个完整的编码解决方案包含配置我们关心的问题时间槽,如图7。随着时间的插槽轮流,每个时间段确定自己的队列的配置和目标条目基于结果以前的时间段和随机的配置决定了它的“下一个跃点”和“通道宽度”条目。重复相同的过程,直到所有的会议都传染给他们的最终目的地。在选择“下一个跃点”和“通道宽度”条目,我们需要考虑造成的影响传输到下一跳,传输干扰约束和不同宽度的信道分配。例如,如果节点之间的传输距离太长,或40 MHz不能用作最大通道宽度,然后删除40 MHz选项,和一个从剩下的选项(5 10或20 MHz)选择分配通道的宽度。在每个时间段内,分配通道宽度和SINR采用香农容量方程来获得系统的激活时间对于每一个时间段,最后所有的时间总结计算总系统激活时间,即能量值的编码系统状态。

3.2.2。代的初始状态

一开始的SA算法,初始系统状态需要决定,这个国家应该匹配最初的解决方案,满足所有前面小节中描述的约束;是,这个系统状态必须永久保持代表的可行性解决方案。考虑传输的会话数网络拓扑、节点的数目,拓扑结构的节点之间的距离,和大小,源节点和目的节点的每个会话是已知的。给出的步骤生成初始状态如下:(我)生成所有队列和目的地在初始时间槽的配置项;(2)在约束(5),一个节点的会话的“队列1”可以选择随机传送和分配的“下一个跃点”条目的会话。如果距离大于两个节点(最大可能的传播范围),然后再次“下一个跃点”条目应该选择会话;(3)由(1)和约束(7),随机选择一个通道宽度选项来确定“通道宽度”条目会话的传播,也就是说,一个在“队列1。“如果没有合适的通道宽度的选择,两个“下一跳”和“通道宽度”条目的会话都设置为0;也就是说,会话将在以后传输插槽;(iv)回到步骤(2),直到所有的通道宽度”和“下一个跃点”条目所决定;(v)如果仍有会话,还没有达到目的地在这个时间段,保持队列和目的地条目,回到步骤(2)在下一个时间段。如果所有的课程在这个时间段已经达到目的地节点、传输过程完成;(vi)计算和总结每个时间段的系统激活时间获得总系统激活时间,初始状态的能量值。

3.2.3。小区选择

本节描述如何搜索周边国家通过SA算法实现迭代改进。考虑当前的系统状态,其中包含配置时间槽。我们随机选择一个时间段。在相邻状态如图8,配置槽0到时间段是一样的当前状态,而配置的时间段时间槽改变使用同样的程序生成初始状态在前面的小节。

考虑示例图8,在这选为分界点生成新的邻近国家。在新的邻近国家,不时槽0到槽的配置作为当前状态保持不变,没有传输到目的地的会话节点在时间槽将传播后时段。如图8新的周边配置,有一个会话(尺寸2.56 mbit)在节点1时间槽和目的地节点仍然是节点6。“下一个跳”和“通道宽度”条目,然后随机选择。形式图8可以看出,新实体,“下一个跃点”= 3,“通道宽度”= 40 MHz时槽不同于当前状态,“下一个跃点”= 5和“通道宽度”= 10 MHz时间槽。遵循同样的步骤,所有会话后会产生一个新的相邻状态传输成功。

注意,新的相邻状态并不一定比当前状态,甚至可能更糟的能源价值。因此,迭代改进过程必须与SA算法进行接受一个劣质的解决方案和跳过局部最优解在优越的可行解或几乎可以找到最优解。

4所示。实验结果和分析

为了评估我们建议的方法的性能,我们实现该算法,进行不同的实验。因为我们联合RSC问题是新的,我们首先比较实验结果对于一个小规模的问题(SINR的不考虑),生成的最优解列生成算法。注意,列生成一个精确的算法,它只适用于小规模的问题。然后,我们评估我们的SA算法的性能对大规模问题关注造成的SINR节点之间的传输范围。我们的算法实现了在c++编程语言和运行在一个英特尔酷睿i5 - 3210米@ 2.50 GHz CPU电脑8 GB内存分析性能。我们的SA算法的参数设置在实验中列出如下:Kotzman参数;最高温度;最低温度;冷却常数;和最大迭代次数。

4.1。实验结果为小规模的问题

我们继续使用这个问题实例(SINR干扰不考虑)和参数设置(11)如下:瓦特= 1米,= 2,瓦特/ MHz,= 1.3。

回想一下,不同宽度的信道分配方案。网络拓扑结构考虑(11使用5 MHz), 10 MHz, 20 MHz, 40 MHz通道宽度数据所示9(一个)- - - - - -9 (d),分别。与图9(一个),图的拓扑结构9 (b)没有链接(1,3),这意味着采用5 MHz通道宽度可以传播得更远。同样,对数字9 (c)和9 (d)分配渠道宽度越大,越短的会话可以传播。本节我们的实验是将三个会话表1在这个拓扑。

网络的问题场景是由我们与5 MHz固定宽度的SA算法,解决40 MHz固定宽度,和不同宽度的信道分配方案,分别与实验结果相比产生的最优解列生成算法给出了表2- - - - - -4。从结果采用5 MHz宽度固定的信道分配方案表2,我们的SA算法可以找到一个解决方案相同的解决方案产生的最优解列生成算法,虽然活动链接的订单是不同的。对于运行时间,我们与5 MHz的SA算法宽度固定信道分配方案只需要3.739秒获得解决方案。

从结果采用40 MHz宽度固定信道分配方案表3总系统激活时间发现,由我们的SA算法2.25908秒,略低于2.11524秒的列生成算法。在这种情况下使用40 MHz宽度固定信道分配方案、分配渠道宽度增加和传播范围减少,和,因此,需要更多的啤酒花SA算法很难获得最优解。然而,我们的算法仍然可以获得近优解21.949秒,显示我们的算法的计算效率。请注意,我们只比较最小和最大宽度固定信道分配方案和不同宽度的信道分配方案,因为10 MHz和20 MHz的结果之间的5 MHz 40 MHz。

从结果表采用不同宽度的通道宽度的计划4,总系统激活时间发现的SA算法1.51011秒,略低于1.33181秒的列生成算法。相比的结果采用5 MHz宽度固定信道分配方案表2,总系统激活时间是4.66991秒更快或显示提高76%;相比的结果采用40 MHz宽度固定信道分配方案表3,总系统激活时间是0.74897秒更快或显示提高33%。因此,可以得出结论,虽然我们与不同宽度的通道宽度的SA算法分配方案可能不会发现最优解作为列生成算法相比,它仍然可以找到高质量的可行的解决方案,它是更有效的比列生成算法。

4.2。实验结果为大规模的问题

本节的重点是会话的数量的变化传输拓扑结构的不同大小来评估不同宽度之间的性能差异和宽度固定信道分配方案。不同的结果在以前的分段,节点位置和节点之间的传输范围的影响被认为反映SINR对信道容量的影响。

4.2.1。准备场景的测试发射5 10-Node网络会话

网络拓扑结构被认为是在这个实验中包含10个节点在一个100米100区域,节点# 1 - # 10图10。在这种拓扑中,我们限制所有10个节点的坐标不大于50,因为使用的空间拓扑减少一半,的概率会话应变可以大大减少。请注意,会话应变指的是事实,一个会话的初始位置恰好是一个异类节点上,即使5 MHz通道宽度的通道宽度(传输会话能力最长的范围),分配会话仍不能传播到下一个节点,导致会话永久应变在初始节点。这个实验的问题在于传播的五个交易日不同交通负荷表510-node网络拓扑。

执行30分的结果我们与不同宽度的SA算法,5 MHz固定宽度,40 MHz宽度固定信道分配方案绘制在图11,很明显看到的性能不同宽度和40 MHz宽度固定信道分配方案比5 MHz宽度固定的计划。的平均总系统激活的时候执行30运行我们的SA算法三个信道分配方案是4.6255,16.1476,和5.3161秒。相比,平均5 MHz宽度固定信道分配方案,不同宽度的计划大约需要11.5秒的时间少,或提高249%,这是真正了不起的。至于40 MHz宽度固定信道分配方案,不同宽度的计划需要0.6906秒的时间少,或15%的改善。

尽管不同宽度的信道分配方案执行比40 MHz固定宽度平均信道分配方案,他们仍然彼此交叉图11和他们的性能差异不是立即可辨别的。因此,以及进行检查,如果不同宽度的信道分配方案执行统计比40 MHz宽度固定的计划。的以及结果表明,列文的测试平等的显著性水平为0.964,大于0.05,暗示方差必须设置相同。在以及用同样的手段,显著性水平为0.012,低于0.05。因此,我们可以得出结论,在95%置信水平,不同宽度的表演和40 MHz宽度固定信道分配方案明显不同,和不同宽度的信道分配方案的总系统激活时间明显短于40 MHz固定宽度的计划。

4.2.2。场景的测试发射7会话10-Node网络

除了五个会话表5、两个会话表6被认为是在同一个网络拓扑在前面的小节中,评估性能和重交通荷载。

执行的结果30分的SA算法同样的问题之前的分段的传输两个会话是绘制在图12,平均总系统激活的时候采用的不同宽度,5 MHz固定宽度,和40 MHz宽度固定信道分配方案是6.2013,20.465,和7.7593秒,分别;也就是说,都是增加与传输5会话的情况相比,增加利率是34.07%,26.74%,和45.96%,分别。这意味着,在相同的拓扑中,交通负载越重,越正交通道需要传输更多的并发会话并减少所需的总系统激活时间。如图12、不同宽度的结果和40 MHz宽度固定信道分配方案不明显相互交叉,和我们以及还表明,显著性水平较高,表明,随着交通负荷的增长,不同宽度的信道分配方案的性能变得更好。

4.3。模拟退火算法的可伸缩性测试

实验增加节点的数量和会话进行评估我们的SA算法的性能在更复杂的网络拓扑与20节点和30个节点,分别为(包含节点20 # 1 - # # 1 - # 30图和节点10、职责)。除了七个交易日中指定的表5和6、三个额外的会话被添加在这个实验中增加传输流量,和他们的信息如表所示7。

执行30的SA算法运行结果传输10 10-node会话,20-node,采用30个节点网络将大大拓展战场如图13,平均总系统的激活时间是14.8829,18.6813,和21.0589秒。在平均,当节点的数量以及问题的复杂性的增加,其结果是更糟糕的是,和更好的解决方案是不可能达到的预期数量增加的可用路径。从图13不同,结果不同的节点数量,表明,条件下,会议传播的数量是相同的,与更多的节点拓扑可以获得一个更好的结果比用更小的数字拓扑节点。虽然我们的SA算法可能并不总是得到最优解,它仍然可以在很短的时间内获得高质量的解决方案。

5。结论和未来的工作

本文提出了一种模拟退火(SA)算法的联合路由、调度、WMNs信道分配问题,在不同宽度的信道分配方案被认为找到一个微妙的平衡之间的相互冲突的目标,如并发会话传输和信号干扰。小说的编码设计SA算法利用本文说明了动态传输过程。我们的实验结果表明,相比于小规模的列生成算法问题,SINR的不考虑,我们的SA算法能获得相同或相似的解决方案产生的最优解列生成算法。相比宽度固定信道分配方案,预先形成的不同宽度的方案比固定宽度的计划。至于可伸缩性测试我们的SA算法,当节点数量的增加,总系统激活时间也会增加。虽然这个结果是由于问题的复杂性和难度的增加,最优路径的识别,导致效率下降,SA算法仍然可以找到一个高质量的可行的解决方案。同时,不同列生成精确的最优解的算法,我们的SA算法更有效解决共同的问题。

的未来的工作是设计解决方案的编码机制,或集成我们的SA算法与其他人工智能的方法来解决这个问题。这也将是移动节点扩展共同感兴趣的问题或调查multiradio多通道版本的共同问题。

利益冲突

作者宣称没有利益冲突有关的出版。

确认

作者感谢匿名裁判的评论改进内容以及本文的演示。这项工作已经被NSC支持部分102 - 2219 - e - 009 - 013, nsc102 - 2410 h156 - 008和102 - 2221 e018 NSC - 012 my3,台湾。