在线算法滑雪板租赁问题在客票系统中的应用
戴琳琳
【摘 要】介绍滑雪板租赁问题的决策算法及符合该类问题模型的应用场景,客票系统中的站车交互系统无线交互协议符合此类问题的应用场景,实现了相关算法,并取得了较好效果.%This article introduced the ski rental problem and its related algorithm, presented the application scenarios in accordance with this kind of problem model. The correlation algorithm was applied to the wireless station-train transmission protocol of railway ticketing and reservation system. It was implemented the correlation algorithm and obtained better results.
【期刊名称】《铁路计算机应用》
【年(卷),期】2017(026)010
【总页数】3页(P21-22,27)
【关键词】在线算法;滑雪板租赁问题;站车无线交互协议
【作 者】戴琳琳
【作者单位】中国铁道科学研究院 电子计算技术研究所, 北京 100081
【正文语种】中 文
【中图分类】U293.22;TP39
滑雪板租赁问题是特指某一类问题，这些问题需要在持续重复花费和一次性付清两种策略间做出选择。这个问题模型也可以应用在其他领域，如在德国铁路优惠卡购买时机问题[1]、移动终端连接管理器进入省电模式时间选择问题、项目管理中是否需要重构代码决策问题，具有较强的应用价值。
铁路站车客运信息无线交互系统总体架构如图1所示[2]，列车工作人员的手持设备通过GSM/GSM-R无线专用网络（APN）接入站车内网[3]，与站车内网中的信息发布服务器进行交互下载文件，信息发布服务器上存放着从客票内网传输过来的客票数据文件。站车手持设备与信息发布服务器的数据交互需要通过GPRS接口服务器进行转接，该接口服务器负责数据包内容检查，对异常数据包进行过滤。由于GPRS接口服务器目前只支持对用户
数据协议（UDP）包转发，因此，客票系统中的无线交互协议（TSWTP，wireless station-train transmission protocol）需要在UDP基础上实现类传输控制协议（TCP）的传输完整性控制，为了简化协议和提高传输效率，TSWTP实现了数据文件分包、数据传输窗口控制以及数据包传输确认。
当客户端向信息发布服务器请求文件时，信息发布服务器将数据文件分包（默认500 byte），按照发送窗口控制，连续发送数据包，在客户端确认后，数据传输窗口移动，直至传输结束。这一过程与TCP实现类似，在传输确认过程中，如果对每个接收到的包都发送传输确认，那么大量的传输确认包会占用大量带宽，而延迟确认可以在接收到一定数量的包后，统一发送一个确认，这样可以减少确认包的数量，但是也不能太迟发送，不然会以为发生拥塞，因此，选择合理的传输确认算法在很大程度上会影响传输协议的效率。
铁路站车客运信息无线交互系统的TSWTP是基于无线传输的，并且系统的无线终端广泛使用在高速铁路列车上。由于高速铁路列车具有较高的移动速度，而这种较高的移动速度会对无线信号传输造成多方面的影响：（1）高速移动速率会增加无线传输的误码率，会对无线传播信号的强度造成影响；（2）列车的高速移动，有高速越区切换的情况。
中国在线编程因此，站车客运信息无线交互系统无线数据传输具有无线传输信息不稳定、传输速率抖动的特点。这一特点使得传输确认问题符合在线算法滑雪板租赁问题（Ski rental Problem）模型。
滑雪板租赁问题原型如下：假设你要去滑雪，但是可以滑雪的天数未知（各种原因：丧失兴趣，受伤，天气恶劣等）。假设滑雪板每天的租赁价格是1，购买滑雪板的花费是N。每天都需要决定今天是租还是买滑雪板[4]。
该问题算法应用在不确定未来情况，但持续在线接收请求，而且每接到一个请求都需要进行决策的问题模型[5]，这与站车无线交互协议的传输确认问题模型一致，在接收数据包后，需要在线判断何时进行数据包确认。
目前，TCP传输确认有如下实现方法：Solaris TCP实现曾采用一个50 ms的内部定时器，当一个包到达后，定时器开始工作，到时后，统一发送所有接收的包的确认；BSD TCP则采用200 ms的定时器，每个200 ms就发送当前接收到包的确认。
这些设置确认定时器的实现方法优点是算法简单，但是这些算法一般基于有线传输，传输
条件比无线传输稳定和优越，而且无法处理高速运动中无线传输速率动态变化的特点，因此需要使用基于动态确认的在线算法来解决问题[6-7]。
Daniel等人提出动态确定定时器时间的基于滑雪板租赁问题的在线算法[8]，该在线算法设置的收支平衡点为发送一个确认包的延迟等于发送一个确认包的代价，具体如下：
假设η∈[0,1]为衡量减少确认包发送个数和减少确认包延迟之间重要性的比例指标，这个系数可以由系统管理员设置，σ为当前统一发送确认包的接收包集合，|σ|为集合里元素的个数。那么在每个新的接收包aj到来后，就根据该算法设置定时器，定时时间是TA，TA满足公式：得到：该算法会使整体延迟不超过
目前，该算法在站车交互系统平台的服务器端实现，编程环境Linux gcc，编程语言C/C++，运行操作系统Redhat Enterprise Linux Server release 5.4。
实际测试中，在运行线路相同，无线网络环境相同，同时传输相同数据，分别记录采用FTP和TSWTP下载在相同和不同速度运行时的相关性能数据，包括数据传输速率（分上行和下行）、文件传输成功率；同时累计增加传输量的情况下对以上数据进行记录，记录结果如图2、表1、表2所示。
由于TSWTP设计简练，与基于FTP的通用数据下载协议相比，性能更好，效率更高，特别是在信号不稳定的高速铁路沿线，定制的数据传输协议对从不稳定无线网络中恢复传输所需要的通信开销更少、速度更快。
客票系统中的站车交互系统无线交互协议符合滑雪板租赁问题的应用场景，实现相关算法并取得了良好效果，滑雪板租赁问题的决策算法具有较强的应用价值。
【相关文献】
[1]Rudolf Fleischer. On The Bahncard Problem[C]. 4th Annual International Computing and Combinatorics Conference(COCOON-98), Taipei (ROC), August , 1998:12-14.
[2]周亮瑾，朱建军，阎志远，等. 铁路站车客运信息无线交互系统的研究[J].铁路计算机应用，2010，19（7）.
[3]武振华，李贝贝，刘相坤，等.铁路站车客运信息列车版无线交互系统的研究[J].铁路计算机应用，2014，23 （10）：20-23.
[4]Maurice Queyranne.An Introduction to Competitive Analysis for Online Optimization[D].British Columbia: University of British Columbia, and IMA Visitor (Fall 2002).
[5]S. Albers.Better bounds for online scheduling[C]. in Proc. 29th Annual ACM Symposium on Theory of Computing (STOC97) ,pages 130-139, 1997.
[6]A. Borodin and R. El Yaniv. Online Computation and Competitive Analysis[D]. England, Cambridge: Cambridge University Press.1998.
[7]Anna R. Karlin, Claire Kenyon and Dana Randall. Dynamic TCP Acknowledgment and Other Stories about e/(e-1) [J].Algorithmica, 2003 , 36 (3) : 209-224
[8]Daniel R. Dooly, Sally A. Goldman and Stephen D.Scott.TCP Dynamic Acknowledgement Delay:Theory and Practice[C].30th Annual ACM symposium on theory of computing(STOC),1998, Dallas, TX, USA, pp. 389-398.

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。