Ad hoc虚拟骨干网中一种费率优先分布式CDS算法

北京邮电大学学报 ›› 2004, Vol. 27 ›› Issue (3): 88-92.

Ad hoc虚拟骨干网中一种费率优先分布式CDS算法

程胜, 张勖, 冯美玉, 丁炜

北京邮电大学宽带通信网络实验室, 北京 100876

收稿日期:2003-06-12 出版日期:2004-03-28
作者简介: 程胜(1976— ), 男, 博士生. E-mail:censen@bupt.edu.cn
丁炜(1935—), 男, 教授, 博士生导师. E-mail: dingwei@bupt.edu.cn
基金资助:
国家自然科学基金项目(60372101); 教育部博士学科点专项科研基金(20020013011)

A Cost-Priority Distributed Algorithm for Connected Dominating Set in Virtual Backbone-Based Mobile Ad hoc Networks

CHENG Sheng, ZHANG Xu, FENG Mei-yu, DING Wei

Broadband Communication Networks Laboratory, Beijing University of Posts and Telecommunications, Beijing 100876, China

Received:2003-06-12 Online:2004-03-28

摘要/Abstract

摘要： 移动Ad hoc网络可以通过构建虚拟骨干网来减少参与路由计算的节点数量。虚拟骨干网可以由近似的最小连接主节点集(MCDS)组成。本文对几种经典的分布式近似MCDS查找算法进行了比较,提出了一种新的费率优先的分布式近似MCDS查找算法,详细介绍了该算法的流程,并对算法的性能进行了分析,仿真结果显示该算法的性能优于经典算法。

关键词: 移动Ad hoc网络, 虚拟骨干网, 最小连接主节点集

Abstract: Building of virtual backbone in mobile Ad hoc networks can effectively reduce the numbers of nodes used to run routing protocols. The virtual backbone consists of minimum connected dominating set (MCDS). Classical MCDS algorithms were compared with in several. A newly cost-priority distributed approximation MCDS algorithm was proposed, in which the flow was introduced. Simulation shows that the performance of the proposed algorithm has advantage over the existed ones.

Key words: mobile Ad hoc networks, virtual backbone, minimum connected dominating set

中图分类号:

TN929.5

程胜, 张勖, 冯美玉, 丁炜. Ad hoc虚拟骨干网中一种费率优先分布式CDS算法[J]. 北京邮电大学学报, 2004, 27(3): 88-92.

CHENG Sheng, ZHANG Xu, FENG Mei-yu, DING Wei. A Cost-Priority Distributed Algorithm for Connected Dominating Set in Virtual Backbone-Based Mobile Ad hoc Networks[J]. JOURNAL OF BEIJING UNIVERSITY OF POSTS AND TELECOM, 2004, 27(3): 88-92.

[1]	翟立东，刘元安，马晓雷，高锦春. 发布/订阅通信机制在移动Ad Hoc网络中的应用[J]. 北京邮电大学学报, 2008, 31(2): 30-33.
[2]	孙斌. 基于MANET虚拟骨干网的密钥管理体系的研究（增刊）[J]. 北京邮电大学学报, 2007, 29(s1): 109-113.
[3]	魏翼飞,张勇,宋梅,宋俊德. 一种适用于WiFi Mesh网络的AODV改进路由协议[J]. 北京邮电大学学报, 2007, 30(4): 120-124.
[4]	郑敏，勾学荣，李新，丁炜. 基于虚拟骨干网的MANETs地址分配方法[J]. 北京邮电大学学报, 2006, 29(4): 111-114.
[5]	程胜, 冯美玉, 张勖, 丁炜. Ad hoc网络中VBDAR分布式[J]. 北京邮电大学学报, 2004, 27(5): 104-108.
[6]	王海涛. 移动Ad hoc网络的分簇算法及性能比较[J]. 北京邮电大学学报, 2004, 27(1): 93-97.
[7]	杨军,李建东. 有效支持智能天线在MANET中应用的多址接入协议[J]. 北京邮电大学学报, 2003, 26(S1): 89-94.