论文部分内容阅读
本文研究在高速运行环境中,基于蜂窝信息站集成网络的非均匀宽下动态效用无线报文调度算法,包括无特定用户带宽限制的调度算法和具有特定用户带宽限制的调度算法。在蜂窝信息站集成网络中,蜂窝网路提供低速较大范围的网络覆盖,在铁路沿线部署信息站,提供小范围内高速网络传输,用户通过蜂窝网络请求数据,数据通过信息站作为网络传输的中转站,传输到车辆站,这种网络集成了信息站和传统蜂窝网络各自的优点,能够为高速铁路环境提供较大范围内的高速传输率。高速铁路等高速运行的环境中,无线网络用户的按需请求服务数据,通过路边的信息站发送到用户终端设备上,而往往该段的调度是整个网络系统的瓶颈所在。为了提高在该环境下用户网络服务体验,为用户提供稳定高效的按需网络服务,同时提高网络提供者获得的总收益,提出了按需服务的无线报文最优调度问题。本文分析两种问题的模型:无特定用户带宽限制的调度问题和具有特定用户带宽限制的调度问题。通过分析两种调度问题的特殊结构,将问题转化为一个整形规划问题,进而将问题转化为0-1规划问题。能够证明,该调度问题是NP问题,不能通过现有算法在多项式时间内求得最优解。我们提出了一种基于新效用函数的贪心算法,并且提出再调度函数,为当前正在调度的数据包找出再调度路径,增加调度的数据包的数量。针对具有特定用户带宽限制的调度问题,将其转化为求解二分图的最大权匹配问题,利用Kuhn-Munkres算法可以在多项式时间内求得近似最优解。首先,我们提出了新的更加一般化的价格(效用)函数,即用户愿意为在不同时间内被调度的数据包所支付的价格是不同的,数据包服务的动态效用化。第二,我们分析了求解非均匀宽下动态效用无线报文调度问题的贪心算法;其次,我们将非均匀宽下动态效用无线报文调度问题转化为加权二分图的最大权匹配问题。通过分析具体问题中的限制条件,修改转化为加权二分图的规则,使得修改后的二分图的一个匹配集合是原调度问题可行解集的一个子集,而最优匹配在原问题中可能不是最优的,但是可以求得近似最优解。最后,我们利用仿真来证明各种算法的优劣性,算法的性能仿真测试了我们提出算法的正确性和优越性,且能够明显提高非均匀宽下动态效用无线报文调度问题的总收益。