基于NS2的优先级队列管理算法设计*

潘丰旻， 江 明， 周加文， 葛 愿

(安徽工程大学，安徽 芜湖 241000)

0 引 言

网络控制系统(Networked Contorl Systems，NCS)于1999年出现在马里兰大学Walsh的论著中，该系统利用通信媒介使控制回路形成闭环[1]。与传统的控制系统不同，它采用多样的网络连接方式提高了系统组件的灵活性，在智能电网、智能交通等领域有着巨大的应用前景[2-3]。融合了计算机技术和通信技术的NCS，除了控制算法影响其性能好坏以外，合理地调度计算机的网络资源也十分必要.NCS的网络服务质量指标包括时延、丢包和吞吐量等。由于网络的不稳定性必然引入时延、丢包等问题[4-6]。因此，要在NCS的网络传输部分采用合适有效的队列管理算法。

进行实验模拟是研究分析NCS性能的高效方法。NCS模拟工具主要包括MATLAB、OPNET以及NS2.MATLAB的TrueTime工具箱在控制策略方面的模拟功能强大，但其网络模块的功能相对薄弱，模拟NCS网络环境中的队列管理机制较为困难；OPNET具有很强的网络功能，但这款商用软件使用费较为高昂；而NS2作为一款开源免费的软件，它采用分裂对象模型的方式，利用Otcl语言搭建网络拓扑结构，C++语言实现具体协议，达到了模拟配置灵活性和仿真运行高效性的统一[7-9]，受到越来越多的重视。如高文宇等人提出的网络仿真软件NS2中队列调度算法的扩展[10]。杨故等提出的基于NS2的改进队列管理算法及其实现[11]。高鹏等人基于NS2的主动队列管理算法的仿真与分析[12]等。为此，本文首先设计NCS中的优先级队列管理算法；其次利用NS2搭建一个网络传输模型，并调用队列管理算法进行仿真实验；最后进行实验数据的分析和实验结果的总结。

1 基于NS2的优先级队列管理算法实现

1.1 队列管理算法

网络业务流以数据分组的形式在网络中传输。它们流经不同网络节点时会采取队列缓存、延迟转发等服务方式，而队列管理的作用就在于此。能通过丢弃或者标记这些数据分组来管理网络传输节点中的队列缓冲资源。队列管理主要分为主动式队列管理及被动式队列管理。主动式队列管理算法通过预测分组的状态特性，在网络拥塞还未发生之前就按照预先的设定进行相应的弃包，从而有效控制队列缓冲区的长度，其中的典型算法为RED；而被动式队列管理算法在队列缓冲区设置了固定的数据分组存储上限，当队列中接收到的分组达到上限值，则启动弃包机制，其中典型算法有DropTail算法。验证队列管理算法性能的好坏，要从业务需求和算法复杂程度出发，结合时延、丢包、吞吐量等因素进行综合讨论,而两种典型算法的算法性能如表1所示。

主动队列管理算法结构较为复杂，增加设备开销，平均时延相对较高，网络吞吐量也相对较低。其参数设置敏感并且网络响应相对滞后，并没有在网络当中得到大量使用；相比之下，虽然被动式队列管理算法丢包率相对较高，但其相对较低的延时特性以及简单的算法结构，在实际网络中仍获得广泛使用。

1.2 PDropTail算法设计

NCS因为系统业务类型复杂，不同业务之间对于网络服务质量往往有着不同需求，需要在保持较低时延和较高吞吐量的基础上进行优先级区分服务。所以新的算法具有优先级识别机制，它在选择弃包方面不再是直接“弃尾”，而是综合考虑了队列中数据分组的优先级情况：当数据分组进入节点的队列缓冲区时，若缓冲区为未满状态，则仍然按照先进先出的原则实行队列管理；若缓冲区为已满状态，则启动优先级识别机制，选取队列缓冲区队头前两个数据分组进行优先级比较。若第一个数据分组的优先级较高，则选择丢弃队列尾的数据分组，否则丢弃队列头。PDropTail队列管理算法原理如图1所示。

表1 队列管理算法性能对比

图1 PDropTail队列管理算法原理图

1.3 PDropTail算法在NS2中的实现

利用NS2仿真软件进行PDropTail算法的设计，首先需要在NS2中进行算法脚本的编译与添加。而PDropTail算法的优先级识别机制和弃包选择机制的部分核心程序代码如下：

void PDropTail::enque(Packet* p)

{

……

int qlimBytes = qlim_ * mean_pktsize_;

if ((!qib_ && (q_->length() + 1) >= qlim_) ||

(qib_&&(q_->byteLength()+hdr_cmn::access(p)

->size()) >= qlimBytes))

{

int prio1,prio2;

prio1=HDR_IP(q_->lookup(0))->prio();

prio2=HDR_IP(q_->lookup(1))->prio();

if(prio2>prio1) {

q_->enque(p);

Packet* pp=q_->deque();

drop(pp);

}

else {

drop(p);

}

} else {

q_->enque(p);

}

}

qib_&&(q_->byteLength()+hdr_cmn::access(p)函数部分是对缓冲区的状态进行判断，若队列为满状态，则启动优先级比较机制对队列头前两个数据分组的优先级prio1和prio2进行比较。该比较机制中若第二个数据分组的优先级更大则强制丢弃队头数据分组drop(pp)；若第一个数据分组优先级大则强制丢弃队尾分组drop(p)。而当队列状态为未满时，数据分组将直接进入队列缓冲区enque(p)。

2 基于NS2的网络模拟与算法性能分析

2.1 搭建网络拓扑结构

利用NS2仿真软件搭建如图2所示的NCS网络传输模型。搭建该模型的步骤包括节点设置以及链路配置两方面。从节点设置方面考虑，标号为8、9的两节点设为路由节点，0、1、2、3节点设为发送节点，4、5、6、7设置为接收节点；从链路配置方面考虑，两路由节点间的瓶颈链路带宽设为1.7 M，时延设为20 ms，其余链路带宽均设为2 M，时延为设10 ms。这样的拓扑结构设计和带宽配置主要为了让数据分组在传输过程中产生一定的网络拥塞情况。

在0到4,1到5,2到6以及3到7链路之间各建立一条UDP联机，并在UDP联机之上建立CBR流量发生器.为了模拟4个不同优先级业务，需要对数据分组的IP包头设置优先级。将4种业务的优先级分别设置为1、2、3、4，其中数字越大为优先级越高，在网络中将获得优先服务。网络模型搭建完成后，分别调用两种算法进行模拟实验，模型正常工作后会出现如下的动画效果如图2所示。网络模型搭建的主要代码如下：

set n8 [MYMns node]

set n9 [MYMns node] //路由节点设置

MYMns duplex-link MYMn8 MYMn9 1.7M 20ms 算法

MYMns queue-limit MYMn8 MYMn9 10

for {set i 0} {MYMi<3} {incr i} {

set s(MYMi) [MYMns node]

set d(MYMi) [MYMns node]

MYMns duplex-link MYMs (MYMi) MYMn8 2M 10ms 算法

MYMns duolex-link MYMn9 MYMd (MYMi) 2M 10ms 算法

//发送节点、接收节点设置以及链路参数配置

set udp (MYMi) [new Agent/UDP]

set null (MYMi) [new Agent/Null]

MYMns attach-agent MYMs (MYMi) MYMudp (MYMi)

MYMns attach-agent MYMd (MYMi) MYMnull (MYMi)

MYMns connect MYMudp (MYMi) MYMnull (MYMi)

MYMudp (MYMi) set fid_ MYMi

MYMudp (MYMi) set prio_ MYMi //建立udp联机

set cbr (MYMi) [new Application/Traffic/CBR]

MYMcbr (MYMi) attach-agent MYMudp (MYMi)

} //cbr流量发生器设置

图2 网络模拟动画效果

2.2 队列管理算法性能分析与比较

调用两种算法下的业务时延情况如图3所示，其中业务cbr1为获得最高优先级的业务，cbr4为优先级最低的业务。调用两种算法下，当模拟时间在0.3 s之前，网络业务量都不断上升，节点缓冲区中的数据分组不断增多导致网络时延不断增大。但此时由于缓冲区为未满状态，队列管理机制仍采取“先进先出”的原则，此时，两种算法下的网络时延情况大体一致。当数据分组在队列缓冲区开始拥塞的情况下，DropTail算法采取“弃尾”机制不停丢弃队尾分组。而PDropTail算法采取优先级识别和弃包选择机制后，高优先级业务获得优先服务，相比DropTail算法就得到了更低的时延。因此两种算法下的时延情况有较大不同。而表2为不同业务流的平均网络时延情况。

图3 两种算法下的时延情况

表2两种算法下的业务流平均时延

算法业务分组时延/scbr1cbr2cbr3cbr4DropTail0.052 0860.064 0970.082 4840.080 544PDropTail0.053 0870.060 7260.066 660.065 628

明显可以看出在调用PDropTail算法时，不同业务的时延基本低于DropTail算法下的时延，事实证明新算法能保证较低的网络时延。而两种算法下的实时网络丢包率情况如图4所示。两种算法的实际网络丢包情况如表3。

图4 两种算法下的丢包率情况

表3两种算法下的业务流丢包情况

算法业务分组丢包(/125个)cbr1cbr2cbr3cbr4DropTail951022313PDropTail92101328

由图形和表格数据可知：两种算法下的实时丢包率均随着模拟时间逐步上升。虽然两种算法情况下的总丢包数保持一样的水平，但是调用PDropTail算法下确保了优先级较高的业务cbr4获得优先服务，保证了其较低的网络丢包情况。 调用两种算法的网络吞吐量情况如图5所示。图5反映了新算法能保持与DropTail算法几乎一致的高吞吐量。因此，通过时延、丢包和吞吐量等方面因素的实验对比分析，验证了新算法对于优先级业务具有一定区分服务的能力，能保证较高优先级业务较低的网络时延和丢包率，也能确保业务在网络传输过程中较高的吞吐量。

图5 两种算法下的吞吐量情况

3 结束语

本文利用NS2对NCS的网络传输模型进行模拟仿真，设计添加了优先级队列管理算法，并在实验中对DropTail算法、PDropTail算法的性能进行了分析比较。从实验数据中可以得出，PDropTail算法能为NCS中具有不同优先级的业务提供更好的区分服务，保证较高优先级业务具有较低的网络传输延时、较低的网络低丢包率，同时也继承了DropTail算法较高吞吐量的优点。因此，实验模拟的结果达到了预期效果。

参考文献：

[1] WALSH G, HONG Y, BUSHNELL L. Stability analysis of networked control systems[J]. American Control Conference, 1999. Proceedings of the 1999 ,14(4):2876-2880

[2] IPACCHI A, ALBUYEH F. Grid of the future[J]. Power and Energy Magazine, IEEE ,2009,7(2):52-62

[3] WANG Feiyue. Parallel Control and Management for Intelligent Transportation Systems: Concepts, Architectures, and Applications[J]. Intelligent Transportation Systems, IEEE Transactions on,2010,11(3):630-638

[4] YUE Dong, HAN Qinglong, CHEN Peng. State feedback controller design of networked control systems[J]. Circuits and Systems II: Express Briefs, IEEE Transactions on,2004,51(11):640-644

[5] WU Jing, CHEN Tongwen. Design of Networked Control Systems With Packet Dropouts[J]. Automatic Control, IEEE Transactions on,2007,52(7):1314-1319

[6]WANG Xiaofeng. LEMMON M. Event-Triggering in Distributed Networked Control Systems[J]. Automatic Control, IEEE Transactions on,2011，56(3):586-601

[7] 徐雷鸣，庞博，赵耀.NS 与网络模拟[M].北京：人民邮电出版社，2003

[8] 于斌，孙斌.NS2 与网络模拟[M].北京：人民邮电出版社，2007

[9] 柯志亨，程荣祥，邓德隽.NS2 仿真实验——多媒体和无线网络通信[M].北京：电子工业出版社，2009

[10] 高文宇,王建新,陈松乔. 网络仿真软件NS2中队列调度算法的扩展[J].系统仿真学报,2006(2):521-525

[11] 杨吉文,张卫东.基于NS2的主动队列管理仿真研究[J].计算机工程，2006(17):189-191

[12] 高鹏,戴旭初. 基于NS的主动队列管理算法的仿真与分析[J]. 计算机仿真,2006(5):98-100,155