无线网络中最小代价空间网络编码算法研究分析.docx

A Dissertation Submitted in Partial Fulfillment of the Requirements for the Degree of Master of Engineering
A Study on Min-cost work Coding Algorithms in works
Candidate: Zhang Zijun
munication and Information System Supervisor:Associate Prof. Huang Jiaqing
HuazhongUniversity of Science and Technology Wuhan, Hubei 430074, P. R. China
January, 2014
独创性声明
本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知,除文中已经标明引用的内容外,本论文不包含任何其他个人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体,均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。
学位论文作者签名: 日期: 年 月 日
学位论文版权使用授权书
本学位论文作者完全了解学校有关保留、使用学位论文的规定,即:学校有权保留并向国家有关部门或机构送交论文的复印件和电子版,允许论文被查阅和借阅。本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据库进行检索,可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。
本论文属于不保密□。
保密□,在 年解密后适用本授权书。
(请在以上方框内打“√”)
学位论文作者签名: 指导教师签名:
日期: 年 月 日 日期: 年 月 日
摘要
work Coding, NC)是一种结合了路由和编码技术的信息交换技术, 在传统存储转发的路由方式基础上,通过允许对接收的多个数据包进行编码融合提高网络的整体性能。Ahlswede 等人于 2000 年提出了网络编码概念,并指出对组播网络中的某些节点附加额外的编码操作能使源与多播成员间的传输速率达到最大流最小割定理给出的上限。空间网络编码问题是近年来出现的一个新方向,它研究信息流在几何空间中的传输,信息可沿空间中的任意路径传输,并且可在任意网络节点上进行编码。
本文研究了无线网络中的最小代价空间网络编码问题,即给定一个无线网络的终端节点的空间位置,以及网络的通信需求(各会话的端到端速率),可在网络的任意位置加入额外的中继节点,探究如何最小化网络的代价。本文将上述代价最小化问题建模为一个线性约束下的非线性规划问题,讨论了其凸性,并提出了求解该规划问题的一般性算法,可给出了联合优化后的路由方案,资源分配方案和中继节点空间位置。此外,本文给出了上述规划问题的降维方法,以降低求解的计算复杂度, 并对求解算法进行了实现和仿真。最后,使用仿真结果对算法进行了解释并分析了仿真结果。
仿真结果显示,通过联合优化路由方案,资源分配方案和中继节点的空间位置, 可有效降低网络的代价,且网络编码不仅帮助简化了问题的建模和求解,还在部分情况下起到了降低网络代价的作用。网络编码技术在无线网络中的应用继承了无线网络固有的复杂性,同时通过对最小代价空间网络编码问题的研究,也进一步揭示了网络编码所带来的优势。
关键词:空间网络编码 无线多跳网络 无线中继 非线性规划
I
Abstract
Network coding is a technique bines coding and routing. Compared with conventional replicate-and forward routing paradigm, network coding enables multiple packets to be coded together in order to improve the performance of et al proposed the concept work coding in 2000, and proved that works where the min-cut max-flow rate cannot be achieved by simple forwarding of packets, coding ing packets at intermediate routers can help achieve the max-flow min-cut rate for works. work Coding has emerged as a new subject work codi