收稿日 期: 2008-09-03; 修 回日 期: 2008-11-27 基金项 目: 湖 南省 教育厅 自然 科学研 究项 目( 05C671) ; 中南 大学 重点创 新基 金资助 项目
( ZB018)
作 者简介 : 张帅( 1983- ) , 男 , 山东 青岛 人, 硕 士研 究生, 主 要 研究 方向 为计 算机 网络 、网络 优化 算法 ( longmao_83@ 163. com) ; 杨路 明 ( 1947- ) ,
男, 教 授, 博导 , 主 要研 究方向 为计 算机网 络; 肖潇 ( 1981-) , 男, 博士 研究生 , 主 要研 究方向 为网络 编码 、网 络 优化 ; 蒲保 兴 ( 1965- ) , 男( 瑶 族 ) , 博 士
研究生 , 主 要研 究方向 为进 化应用 计算、网 络优化 .
基 于 随 机 线 性 网 络 编 码 的 改 善
无 线 网 络 广 播 能 量 效 率 的 方 法
*
张 帅, 杨路明, 肖 潇, 蒲保兴
( 中南 大学 信息 科学 与工 程学 院 计算 机系 , 长沙 410083)
摘 要: 提 出了 一种 应用 网络 编码 技术 改善 无线网 络广 播能 量效 率的 分布 式完 全编 码 广 播策 略 ( DAEBNC) , 其
核心 思想是 发送 节点 通过 获得 邻居 节点 记录 数据的 情况 , 应用 随机线 性网 络编 码选 择多 个源 数据 包 生 成编 码 组
合包 , 依 次发 送; 接收 节点 使用 线性 运算解 码编 码包 获得 源数 据包 。理论 分析 表明 , 该 方法 编 码包 在 所 有接 收 节
点具 有可 解性 , 有 效地 减少 了数 据广播 次数 。仿 真结 果证 实, 与普 通泛 洪方 法相比 , DAEBNC 可以 有 效 地提 高 能
量利 用效 率, 改善 无线 网络 性能 。
关键 词: 随 机线 性网 络编 码; 无 线网 络广 播; 能 量效 率
中图 分类 号: TP393 文 献标 志码: A 文 章编 号: 1001-3695( 2009) 06-2244-04
doi: 10. 3969/j. issn. 1001-3695. 2009. 06.074
Random linear network coding approach to improve energy
efficiency in wireless networks broadcasting
ZHANG Shuai, YANG Lu-ming, XIAO Xiao, PU Bao-xing
( Dept. of Computer, Institute of Information Science & Engineering, Central South University, Changsha 410083, China)
Abstract: This paper presented a distributed always encoded broadcasting based on network coding ( DAEBNC) algorithm to
improve energy efficiency in wireless networks. Itsmain ideawas that based on which packets its neighbors had, the sentnode
chose source packets to generate several linearly independent combinations based on randomlinear network coding and broad-
casts in turn. Then received nodes solved a systemof linear equations to decode combined packets and retrieved source pack-
ets. Theoretic analysisrevealed that encoded packets based on the approach could be decoded in all received nodes, which ef-
fectivelyreduced the number of transmissions. Simulation results indicate that comparingwith existingflooding algorithm, this
approach can effectively improve energy efficiency and consequently improve the performance of wireless networks.
Key words: randomlinear network coding; wireless networks broadcasting; energy efficiency
广播通信是无线网络的一种常用通信方式, 在寻找到达某
一指定节点的路径、向全 网发送 报警信 号、分布式计 算等方 面
得到广泛的应用。由于无线网络节点的移动特性, 使得节点很
难获 得 整 个 网 络 的 拓 扑 信 息, 因 而 广 播 操 作 通 常 采 用 泛 洪
( flooding algorithm) 方法。然 而, 泛 洪方 法会 导 致巨 大的 能 量
开销, 直接影响到无线节 点电池 的寿命, 因此 如何利 用现有 的
网络资源、减少广播开销、提高 能量利 用效率 成为研 究的热 点
之一。
2002 年, Zagalj 等人
[ 1]
证 明, 最小 化 能 量广 播 问 题 是 NP
完全问题。在该问题的研究中, 很多发送算法或方法上改进的
思想被提出。通 常, 这些 算 法或 方法 或 以一 定 的概 率转 发 信
息
[ 2,3]
, 或 基 于 某 种 形 式 的 拓 扑 控 制 来 实 现
[ 4 ~6]
。2000 年,
Ahlswede 等人
[ 7]
基于网络信息 流的概 念提出 了网络 编码的 思
想, 允许节点对信息进行编码, 从而提高网络传输性能。之后,
网络编码被应用于各个方面 的研究, 用 于提高 网络吞 吐量、安
全性等。
无线链路的不可靠性和物 理层的 广播特 性使得 网络编 码
在能量利用效率方面有着很好的应用, 也为最小化能量广播问
题提 供了 一种 新的 途径。Wu 等人
[ 8,9]
证 明在 无线 Ad hoc 网
络组播时应用网络编码, 可以将最小化每位数据能量消耗问题
归结为线性问题, 同时提出了动态拓扑组播的最小化能量解决
方法。Lun 等人
[ 10,11]
提出了 选择最 小能量 多播树 的分 布式 算
法, 并提出了固定拓扑的无线组播网络编码最小化能量解决方
法。Katti 等 人
[ 12]
构 造 了 无 线 Mesh 网 使 用 网 络 编 码 体 系
COPE, 并利用 29 个 802. 11b 节点的实验平台证实能显 著减少
平均传输次数。
1 随机线性网络编码的基本原理
随机线性网络编码方法的 核心思 想是利 用节点 的运算 能
力, 在发送节点线性编码组 合不同 的信息 包, 在接收 节点获 得
足够的线性编码组合后, 通 过运算 得到原 始信息 包, 其可用 性
推广了网络编码理论的应用范围
[ 13]
。
第 26 卷第 6 期
2009 年 6 月
计 算 机 应 用 研 究
Application Research of Computers
Vol. 26 No. 6
Jun. 2009