基于索引和压缩的超高速路由查找及更新算法

在下一代核心路由器的研究中,需要在规定的硬件成本和功耗限制下同时实现超高速路由表的查找和更新是目前研究的难点.论文提出了一个全新的超高速路由表查找及更新算法.该算法采用了基于索引和路由表隐式压缩的方案,不仅实现了可以在每一个SRAM的访问延时周期内输出一个路由查找结果,而且能够在两次SRAM的读写访问延时下完成路由更新.该算法功耗小,存储效率高,整个路由表的信息都可存放在容量接近于1M字节的SRAM中.

满足强连通性的有向团枚举算法研究

有向图的有向边可以表示关系的指向或者数据的传递,在稠密子图的挖掘中引入连通性的约束可以增加顶点之间的联系。为此,结合极大团与强连通分量的定义,底图是完全子图且顶点之间满足强连通性的子图结构被称为有向团。已有工作给出了枚举极大有向团的输出敏感算法,然而其存在大量重复枚举和判重操作复杂等不足之处。为了解决这些问题,基于深度优先搜索的思想和有向团的扩展性质,提出一种新颖的递归枚举算法。算法对于出边邻居和入边邻居分别划分候选集与排除集,维护完全子图结构的同时,不断尝试扩展有向团并保证满足强连通性,并且引入基于共同邻居的支撑点剪枝策略,在稠密图上获得上千倍的效率优化。算法还针对搜索空间给出两种优化设计:一是添加了分割子图的预处理,限制递归调用的搜索范围;二是基于位向量压缩表示顶点集合,提高集合运算的效率。在真实图数据上的实验结果表明,相比现有工作中的输出敏感算法,提出的算法具有50倍以上的加速比。

基于LoRaWAN的自适应多帧高效传输方法

针对LoRaWAN协议中LoRa网关与LoRa终端间数据多帧传输方式存在控制开销和传输时延较大的问题,提出一种基于LoRaWAN的自适应多帧高效传输方法(adaptive multi-frame efficient transmission,AMFET),包含自适应多帧发送机制、自适应多帧接收确认机制和丢帧识别机制。自适应多帧发送机制对需确认数据消息设置优先等级,对高级需确认数据消息进行立即确认,对低级需确认数据消息在自适应发送模式结束后统一进行确认,同时将Fpending机制引入LoRaWAN上行多帧传输;自适应多帧接收确认机制通过位向量压缩技术记录已接收数据帧信息,从而单次对多个需确认数据消息进行合并确认;丢帧识别机制利用需确认帧编号(confirmed data identity,CDID)识别低级需确认消息是否丢失,避免终端异常进入休眠模式。通过数学分析和实验测试,分别对AMFET方法的性能进行了理论验证和实验验证,验证结果表明,相对于原LoRaWAN多帧传输方式,AMFET方法在保证数据传输可靠性的前提下,有效降低了数据传输时延和数据传输能耗。