一种无线传感网中最优传输路径选择的高效算法
2012-08-06葛丽芳
葛丽芳
（福建工程学院 计算机与信息科学系，福建 福州 350108）
1 引言
随着无线传感技术的发展和不同应用场景的需求，支持多媒体数据传输的无线传感器网络具有重要的作用.随着网络规模的扩大，数据流量的急剧增加，由于无线传感网节点计算、存储资源有限，而且部分节点采用电池供电，大量的数据传输导致节点能耗过大，使无线传感网的性能乃至正常工作寿命急剧降低.因此，如何在无线传感器网络中动态选择高效的传输路径对平衡网络资源，延长网络寿命具有非常重要的意义.
支持多媒体数据传输的无线传感网通常由具有处理能力、存储能力与无线通信能力的多媒体传感器节点构成,其通过集成于节点上的多媒体传感器协作地感知外部环境,将图像、音频、视频等多媒体信息传输给终端用户.在应用过程中，流媒体数据对网络服务质量（QoS，如带宽、时延、丢包率等）有严格的要求.为了保障网络的生存时间，需要平衡网络负载，选择具有较高能量的节点传输.同时，为了保障传输质量和时延，需要对传输路径进行跳数限制.
在建模过程中，无线传感网通常被模拟为由众多顶点和连接各个顶点的边组成的图，其中顶点表示为无线传感器节点，而边则是连接各个传感器节点之间的无线信道.某条传输路径中的可用资源可以近似地计算为无线传感器网络负载的倒数，即链路长度/数据流量.无线传感器网络中最优传输路径的发现、选择和收敛性分析方法和相关算法近年来受到研究人员的广泛关注[1].当前无线传感器网络中，用于海量数据传输的路由协议主要是基于QoS感知路由协议[2].早期QoS感知的路由算法仅仅考虑单个QoS参数要求，如仅仅是网络传输的实时性，或数据传输的可靠性等[3].SAR路由协议[4]是无线传感器网络中第一个QoS感知多路径路由选择算法，其在选择路由时不仅会考虑每条链路的端到端时延，还可以计算路径的能耗以及数据包优先级，但路由算法非常复杂，需要维护多个树结构，同时其算法的时间复杂度较高，因此并不适合拓扑变化频繁的无线传感器网络[5].本文研究的目标是提出一种具有多项式时间复杂度的高效算法能够准确快速地找到无线传感器网络中具有最优传输路径（即具有最小负载的传输路径）.
2 无线传感网中最优传输路径求解算法
2.1 无线传感网中最优传输路径问题
定义1 无线传感网中传输路径的容量（负载的倒数）定义为：C=L/N，其中N为该路径中(包括上行和下行的)数据流量，L为链路的长度（跳数）.
定义2 无线传感网定义为：具有n个节点的无向图G=
定义3 无线传感网中最优传输路径选择问题定义为：计算生成树Tr中的一个子树满足链路长度范围：Lmin≤∑e∈ELe≤Lmax和容量∑e∈ELe/∑e∈ENe在所有子树中为最大.
2.2 求解算法
本文求解最优传输路径算法采用动态规划[6]技术实现，其的特点是借助优化子结构T'[7]简化搜索过程.
引理1 假设T'为T中具有最大容量的子树，r'为T'的根节点，令 childT’(r’)={v1,v2,…vq}(childT(r’))，对于 1≤i≤q则每个子树T'vi即是Tvi的最大容量子树.
证明 用反证法，对于1≤i≤q，假设存在另外一个根节点为 vj的子树 T"满足∑v∈V(T'vj)<∑v∈V(T")，则有 T'-T'vj+T"是另外一个以r'为根节点的子树且其容量大于T'，这和题设矛盾，命题得证.
对于树中的非叶节点v，设其有子节点v1,v2,…vdeg(v)，其中deg(v)为节点v的子节点数目，设Ψyv[x]为以v1,v2,…vy为根节点的子树中具有最大容量的子树，其链路总长度为x，设Ωv[x]为以v为根节点的树Tv的子树中具有最大容量的子树，其链路总长度为x.
根据引理1，对于T中的叶节点v，如果x=Lv则有Ωv[x]=Nv否则Ωv[x]=Null，对于具有deg(v)个子节点的非叶节点v有
同时为了构建最大容量子树，需要建立一个缓存来记录遍历过程的中间信息：
算法1给出了计算无线传感网中具有最大容量子树的算法的具体实现.
算法1最大容量路径计算MCP(T,r,Lmin,Lmax)
输入：n节点路网生成树T，路径长度范围区间[Lmin,Lmax].
输出：路径P满足路径长度范围：Lmin≤∑e∈ELe≤Lmax和路径容量∑e∈ELe/∑e∈ENe在所有路径中最大.
1: 计算所有节点v∈V(T)的深度dep(v)
2:FOR每个节点v按照其深度降序DO
3:IFv是叶节点THEN
4: Ωv[Lv]←Nv
5:ELSE
6: FORy←1 TO deg(v)DO
7: FOR x←0v TO Lmax-Lv DO
IF y==1 THEN
10: ELSE
13: END IF
14: END FOR
15: END FOR
16:FOR x←Lvv TO Lmax DO
18: END FOR
19:END IF
20:END FOR
21:x←x-Lv;m←deg(v)
22:P←v
23:WHILE x>0 DO
25:IF L<>0THEN
26: x←x-Lv-Lpar(v)
27:END IF
28:m←m-1
29:END WHILE
30:RETURN P
2.3 算法时间复杂度分析
定理1 具有n个节点的无线传感网生成树中限长(Lmin≤∑e∈ELe≤Lmax)最大容量路径算法可以在)时间复杂度内实现.
证明 在给定最大传输容量生成树的基础上，所有节点的深度可以通过广度优先算法以O(n)的时间计算出.根据引理1和引理2以及算法1中的行2-20可知，所有节点的元素]以及的计算可以在)的时间复杂度内实现.具有最大传输容量的子树也可以在O(n)的时间内计算出来，所以命题得证.
3 结论
无线传感网中最大容量链路的发现和选择能够在解决大量数据的高效传输问题.由于支持多媒体数据传输的无线传感网中数据流量的急剧增加，节点计算、存储资源受限，而且部分节点采用电池供电，难以在高速数据通信中维持较长时间的正常工作.因此，如何在无线传感器网络中动态选择高效的传输路径对平衡网络资源，延长网络寿命具有非常重要的意义.本文针对无线传感网中的限长最优传输路径的求解问题提出一种更优的算法.该算法能以多项式时间)找到限长的最优传输路径，并给出了算法的时间复杂度分析和证明.
〔1〕Shafiullah GM,Gyasi-Agyei A,Wolfs PJ.A survey of energy-efficient and QoS-aware routing protocols for wireless sensor networks.In:Proc.of the Int’l Conf.on Telecommunicatios and Networking/Int’l Conf.on Industrial Electronics,Technology and Automation.Univ Bridgeport:IEEE,2008.352-357.[doi:10.1007/978-1-4020-8737-0_63].
〔2〕Sohrabi K,Gao J,Ailawadhi V,Pottie GJ.Protocols for self-organization of a wireless sensor network.IEEE Personal Communications,2000,7(5):16?27.[doi:10.1109/98.878532].
〔3〕Tian H,Stankovic JA,Lu CY,Abdelzaher T.SPEED:A stateless protocol for real-time communication in sensor networks.In:Proc.of the 23rd Int’l Conf.on Distributed Computing Systems Workshops.Providence:IEEE Computer Society,2002.46?55.[doi:10.1109/ICDCS.2003.1203451].
〔4〕Felemban E,Lee CG,Ekici E.MMSPEED:Multipath multi-SPEED protocol for QoS guarantee of reliability and timeliness in wireless sensor networks.IEEE Trans.on Mobile Computing,2006,5(6):738?754.[doi:10.1109/TMC.2006.79].
〔5〕Man Lung Yiu,Dimitris Papadias,Nikos Mamoulis,Yufei Tao:Reverse Nearest Neighbors in Large Graphs[J].IEEE Transaction on Knowledge and Data Engineering,2006,18(4):540-553.
〔6〕Su HH,Lu CL,Tang CY,An improved algorithm for finding a length-constrained maximum-density subtree in a tree[J].Information Process Letters,2008,109:161–164.
〔7〕Lin RR,Kuo WH,Chao KM,Finding a length-constrained maximum-density path in a tree[J].Journal of Combination Optimization,2005,9(2):147–156.
