一种基于信号机制的能量感知地理路由算法

在实际的无线传感器网络中,由于路由空洞的存在,采用边缘转发机制的地理路由算法容易使空洞边缘的节点由于负载较重,能量快速消耗从而过早的死亡,导致空洞进一步的扩大.为了使网络负载更加均衡,延长网络生命周期,提出了一种基于能量信号机制的地理路由算法SIENGR.SIENGR将节点的初始能量划分3个能量区间,并用能量信号来标识节点的剩余能量所处的能量区间.SIENGR算法的边缘转发机制结合节点的能量信号,利用空洞边界节点的所有平面邻居节点来轮流承担边缘转发的数据量,使产生的路由能够根据节点能耗的情况,自适应地避开空洞边缘能量较少的热区节点,均衡热区附近节点的能量消耗,防止空洞扩大.仿真结果验证了SIENGR算法在网络生命周期、网络能耗均衡、数据包到达率等指标上的性能.

一种基于两跳邻居信息的贪婪地理路由算法

基于地理信息的路由算法由于其高效、低路由开销和良好的可扩展性等特点,在无线传感器网络中得到比较广泛的应用.许多采用贪婪策略作为其基本数据转发机制的地理路由算法都不可避免会遇到路由空洞现象.针对这个问题,本文提出了一种基于掌握两跳邻居节点位置信息的贪婪地理路由算法——Greedy-2算法.该算法能够使节点提前意识到路由空洞的存在,从而尽可能使数据包及时绕开空洞边界节点,减少路由空洞发生的概率,提高分组到达率.对于Greedy-2算法仍然遭遇路由空洞现象的情况,文章提出了一种基于两跳邻居信息的平面化算法PATN,该算法不需要增加额外的平面化开销,即可将网络平面化以采取边缘恢复机制,在UDG网络中保证数据可靠传输.仿真结果表明,与基于一跳邻居节点位置信息的贪婪算法相比,Greedy-2算法可以明显减少路由空洞现象发生的次数,在分组到达率和数据传送的路由跳数方面都有着更好的性能.Greedy-2算法与PATN规则结合后的GPSR-2算法也比GP-SR算法有着更优化的路由跳数.

球面上的K最近邻查询算法

针对球面上数据对象点集的特征和K最近邻查询的需求,提出2种处理球面上K最近邻查询的算法:基于查询轴的K最近邻查询算法(PAM方法)和基于查询圆面的K最近邻查询算法(PCM方法)。对2种算法进行实验比较,结果表明。

平面图的严格邻点可区别染色

图G的严格邻点可区别边染色是一个正常边染色,使得每对相邻顶点所关联的边的颜色集合互不包含.G的严格邻点可区别边色数χ’snd(G)是使G有一个严格邻点可区别k-边染色的最小整数k.本领域存在一个重要猜想:除去一个特殊图HΔ外,每个没有叶子的简单图G都满足χ’snd(G)≤2Δ.当前最好的已知上界是χ’snd(G)≤3Δ-1.一个自然而有趣的问题是,哪类没有叶子的图满足χ’snd(G)≤Δ+C,其中C是一个不依赖于最大度Δ的常数?本文部分地回答了这个问题,即证明了对围长至少为5的平面图G,有χ’snd(G)≤Δ+25.这里围长大于等于5的条件不能被减弱到小于等于4的情形.

若干冠图的邻和可区别全可选性

根据冠图的结构特征,构造了一种染色方案,得到对于有最大度限制的子立方体图和子立方体图的冠图,可平面图和子立方体图的冠图以及可平面图和可平面图的冠图列表邻和可区别全染色猜想成立.进而,对于上述图邻和可区别全染色猜想亦成立.