基于Cayley 图的跨层定向扩散路由算法

华南理工大学学报(自然科学版) ›› 2012, Vol. 40 ›› Issue (6): 118-125.

基于Cayley 图的跨层定向扩散路由算法

李岚^1,2肖文俊³

1．华南理工大学计算机科学与工程学院，广东广州 510006; 2．南昌大学软件学院，江西南昌 330047;3．华南理工大学软件学院，广东广州 510006

收稿日期:2011-03-25 修回日期:2012-01-12 出版日期:2012-06-25 发布日期:2012-05-03
通信作者: 李岚(1978-) ，女，博士生，副教授，主要从事无线传感器网络、并行与分布式计算、代数图论等的研究． E-mail:l.lan03@mail.scut.edu.cn
作者简介:李岚(1978-) ，女，博士生，副教授，主要从事无线传感器网络、并行与分布式计算、代数图论等的研究．
基金资助:
国家自然科学基金资助项目( 60973150， 61170313) ; 江西省自然科学基金资助项目( 2011ZBAB211003)

Cross-Layer Directed Diffusion Routing Algorithm Based on Cayley Graph

Li Lan^1,2Wen-jun³

1. School of Computer Science and Engineering,South China University of Technology,Guangzhou 510006,Guangdong,China; 2. School of Software, Nanchang University,Nanchang 330047,Jiangxi,China; 3. School of Software,South China University of Technology,Guangzhou 510006, Guangdong, China

Received:2011-03-25 Revised:2012-01-12 Online:2012-06-25 Published:2012-05-03
Contact: 李岚(1978-) ，女，博士生，副教授，主要从事无线传感器网络、并行与分布式计算、代数图论等的研究． E-mail:l.lan03@mail.scut.edu.cn
About author:李岚(1978-) ，女，博士生，副教授，主要从事无线传感器网络、并行与分布式计算、代数图论等的研究．
Supported by:
国家自然科学基金资助项目( 60973150， 61170313) ; 江西省自然科学基金资助项目( 2011ZBAB211003)

摘要/Abstract

摘要： 为提高无线传感器网络的能量利用率，采用图嵌入的方法在MAC 层设计固定信道分配协议，在此基础上使用跨层路由协议改进了定向扩散的路由协议，提出一种基于Cayley 图的跨层定向扩散路由算法( CLDD) ．模型采用的图嵌入方法以Cayley 图为逻辑拓扑结构，它具有点对称性质且网络直径达到O( log₂N) ，这使下一跳路由简单、平均路由长度缩小，而且使系统具有高聚集性及鲁棒性．仿真实验表明，CLDD 在系统能耗以及传输时延等方面均优于定向扩散算法和Omniscient Multicast 算法．

关键词: 无线传感器网络, 能量利用率, MAC 协议, 路由算法, 跨层设计, 图嵌入

Abstract:

In order to improve the energy utilization of wireless sensor networks,a fixed-channel allocation protocol is designed in MAC layer via the graph embedding,based on which the directed diffusion routing protocol is improved through a cross-layer approach,and a cross-layer directed diffusion ( CLDD) routing algorithm is presented based on the Cayley graph. In the presented graph embedding method,the Cayley graph is used as the logical topology with vertex symmetry and with a network diameter of O( log₂N) ,which simplifies the next hop routing and shortens the average routing length and,furthermore,improves the integrity and robustness of the system. Simulated results indicate that CLDD algorithm is superior to the directed diffusion algorithm and the Omniscient Multicast algorithm in terms of energy consumption and transmission delay.

Key words: wireless sensor networks, energy utilization, MAC protocol, routing algorithm, cross-layer design, graph embedding

中图分类号:

TP393

李岚肖文俊. 基于Cayley 图的跨层定向扩散路由算法[J]. 华南理工大学学报(自然科学版), 2012, 40(6): 118-125.

Li Lan Wen-jun. Cross-Layer Directed Diffusion Routing Algorithm Based on Cayley Graph[J]. Journal of South China University of Technology(Natural Science Edition), 2012, 40(6): 118-125.

[1]	李梅生肖文俊赖正文张占英韩冬. 一种具有小世界性常数度的数据中心网[J]. 华南理工大学学报（自然科学版）, 2017, 45(7): 63-68.
[2]	阔永红周碧荣陈健. 无线携能协作传感器网络的能效研究[J]. 华南理工大学学报（自然科学版）, 2017, 45(12): 36-42.
[3]	康文雄许耀钊. 节点约束型最短路径的分层Dijkstra 算法[J]. 华南理工大学学报（自然科学版）, 2017, 45(1): 66-73.
[4]	郭黎利高飞孙志国. 基于局部软决策的分布式检测算法[J]. 华南理工大学学报（自然科学版）, 2016, 44(1): 16-21.
[5]	王卫星黄虹孙道宗李亮斌胡子昂. 基于能量异构的 WSN 多链路算法[J]. 华南理工大学学报（自然科学版）, 2015, 43(9): 74-80.
[6]	徐方张沪寅徐宁汪志勇. 基于上下文认知的高能效路由算法[J]. 华南理工大学学报（自然科学版）, 2015, 43(5): 139-144.
[7]	黄智勇张欣. 基于估距方式分类的无线传感器网络定位算法[J]. 华南理工大学学报（自然科学版）, 2014, 42(1): 77-83.
[8]	侯剑儒陈晓敏. 改进的 SpaceWire 路由算法[J]. 华南理工大学学报（自然科学版）, 2013, 41(9): 95-99,106.
[9]	胡小青胥布工文莎刘永桂. 一种能量平衡的最优分布式成簇机制[J]. 华南理工大学学报(自然科学版), 2012, 40(8): 1-7.
[10]	吴玉成李江雯. 基于最优节点通信半径的改进DV-Hop 定位算法[J]. 华南理工大学学报(自然科学版), 2012, 40(6): 36-42.
[11]	李岚肖文俊魏文红. 基于Borel亚循环拓扑的无线传感器网络路由算法[J]. 华南理工大学学报(自然科学版), 2012, 40(4): 30-36.
[12]	张文柱赵贝. 基于梯度和模糊神经网络的容迟网络路由算法[J]. 华南理工大学学报(自然科学版), 2012, 40(3): 57-63.
[13]	胥布工刘贵云. 基于无线传感器网络的鲁棒分布式估计[J]. 华南理工大学学报(自然科学版), 2012, 40(10): 198-202.
[14]	李志杰方旭明. MIMO-WLAN 的帧聚合优化方案[J]. 华南理工大学学报（自然科学版）, 2011, 39(7): 56-62,69.
[15]	莫磊胥布工. 无线传感器网络的目标跟踪能量优化策略[J]. 华南理工大学学报（自然科学版）, 2011, 39(7): 13-20.