基于连通支配树的异构传感器网络拓扑修复算法

由于目前缺乏对异构传感器网络拓扑修复算法的研究,提出了一种基于连通支配树的异构传感器网络拓扑修复算法(HSNTR)。首先,算法以很小的代价构造出用于数据转发的虚拟骨干网,然后,当节点失效时,算法对骨干网进行动态地局部修复以使其仍然连通和覆盖所有节点。理论分析证明了算法在构造和修复骨干网时使用的最大节点数。仿真分析表明了算法在能效性、扩展性和可靠性等方面都优于其他算法。

基于控制流图支配树的测试数据灰度编码生成

为进一步提高数据测试算法性能,提出一种基于控制流图支配树的测试数据灰度编码进化生成算法。利用三角分类程序示例构建数据测试的数据流控制流图,并利用其支配树关系构建测试数据的数据流分析,建立程序变量间的支配关系集。结合遗传算法并利用支配关系及分支距离构建测试数据生成的适应值函数,同时在应用遗传算法时,采用灰度编码方式取代二进制编码,简化编码更新过程。通过在测试程序样例中的实验对比显示,所提方法在平均数据生成数、平均收敛比率和数据生成数分布三个评价指标上得到明显提升。

基于学习自动机的最小连通支配集算法

为解决连通支配集的最小化问题,提出基于改进的分布式学习自动机的近似算法,在分布式学习自动机按随机选择进行深度搜索的基础上考虑回溯策略。该算法构造的是网络中的一棵支配树,只需要节点的局部信息。在网络建模图——单位圆盘图上对支配树性质进行分析和模拟实验。实验结果表明,与现有算法相比,该算法能得到更优的最小连通支配集。

求解圆盘图中最小连通支配集的近似算法

针对无线传感器网络常用的拓扑模型单位圆盘图,提出了基于分布式贪心策略的近似算法DDT,在算法执行的每一轮中,根据一跳邻域范围内的权值和邻居的状态信息,选举出节点并和已确定的节点连接,逐步构造出网络图中的一个支配树。用概率方法研究了支配树中的节点度的性质,通过对极大独立集和最小连通支配集之间关系的分析,得到单位圆盘图中最小连通支配集问题一个新的近似比。计算结果表明,和相关的分布式算法相比,DDT产生的连通支配集在规模上更优。

一种路径覆盖自动生成的改进方法

路径覆盖是考察软件测试充分性的一种重要准则,它使程序的每个分支至少执行一次。该文通过对DDGRAPH图的定义及相关概念的分析,对构建DDGRAPH图及支配树、蕴含树、非限制弧的方法进行了改进。通过具体的应用实例对比了改进前后的方法,改进后的方法可以减少生成的路径数,用更少的测试用例发现更多的错误。

路径覆盖自动生成技术研究

路径覆盖是路径测试最重要的课题之一。文章给出了ddgraph图的支配树、蕴含树和非限制弧的构造方法,提出了一种基于最小路径测试子集的寻找单个测试路径算法,该算法可有效地生成从入口到出口且覆盖非限制弧的路径子集,并给出了具体的应用实例。