（计算机应用技术专业论文）无线传感器网络中传输层无损数据融合技术研究.pdf

中图分类号： u d c ： 学校代码：1 0 0 5 5 密级：公开 蛊蕊犬凑 硕士学位论文 is 7 5 时，随着p l 增长，舻的增长率明显增大很多，这说明在链路稳定性比较 高的情况下，无损融合会给数据传输性能带来更多的提升，更大程度的减少传 输的平均传输开销。 图2 3i i = 1 2 ，h = l ，p l = o 8 时，a t c k 与k 的函数关系 图2 3 给出了在链路稳定性p l = o 8 时，a t c k 与k 之间的函数关系，如此图 所示，并非k 值越大平均传输开销越低，换句话说，并不是在传输过程中融合到 一个数据包内继续传输的信息元越多越好，而是存在某一个负载率的阈值，图 2 3 的情况中，最优的k 值大约为9 ，在负载率小于9 时，负载率的提高会降低 平均传输开销，而在超过该阂值范围之外时，k 值的继续增大会造成平均传输开 1 7 第二章相关研究的理论基础 销的增加，从而造成整个网络的性能下降。这也证明了第一章中的推断，在一 定范围下，无损融合会给整个网络的传输性能带来一定的提升，因此本文将对 无损融合的调度以及对其网络性能的提升进行研究与验证。 在此需要说明的是，本节上述分析均基于单跳链路，而信道稳定性无论在 单跳链路还是多跳链路中均反映了信道中衰退与碰撞所产生的影响，另外，在 多跳链路中，由于数据包大小增加而产生的传输时间增加要比相邻数据包的传 输间隔小的多，因此以上研究也可移植到多跳链路中。更进一步说，基于上述 研究，无损融合会使得网内传输的数据包的数量减少，并在一定范围内使其所 带来的利润大于其开销，从而减少信道中的碰撞与干扰，提高链路稳定性，本 文第五章将通过基于测试床的实验对上述各种因素的作用及影响进行验证。 第二节无损数据融合与数据传输延时 本章第一节以传输次数( 包括重传次数) 的期望与数据包中有效负载大小 的比值为标准，简单论证了无损数据融合对网络传输平均传输开销的降低以及 对其他传输性能的提升。而从另一方面来讲，现实应用中的无线传感器网络中 的数据包必然不会同时到达融合节点，所以当一个数据包到达上层节点时，需 要延迟一段时间来等待其他数据包的到来，因此，封装到一个数据包中的信息 元越多，数据包被重传的可能性会越大，由于等待封装而造成的传输延时也就 越长。在无线传感器网络的现实应用中，每个生成并发出的信息元均有一定的 实用价值，因此在一定的时间范围内，数据包必须送达s i n k 节点处，若传输途 中延迟时间过长造成传输延时超过最大允许延时，该数据包的价值就不存在了， 这里将该数据包在最大允许延时内的价值特性称为数据的时效性。 从数据的时效性来讲，若封装到一个数据包中的信息元过多，必然导致其 中的数据需要较长时间才能送达s i n k 节点，因此对于上一节中提到的负载率， 可以再次肯定的是，负载率不是越高越好，而需要对其加上一个约束条件，使 其满足数据包的时效性。而不同的传感器网络有不同的信息搜集需求，因而最 大的数据传输延迟时间丁也是不同的，若在超过丁的延迟后获得数据，则数据 将会变成无效的，经过的传输过程与节点的能耗就浪费了。因此，在肯定无损 融合给网络传输性能带来提升的前提下，如何将最大传输延迟时间合理的分配 并在各个节点上分布式的加以利用，就变成一个值得关注的问题了。本文将基 1 8 第二章相关研究的理论基础 于传输开销和传输延时利用率，提出了一种面向无损融合的传输调度算法，具 体内容将在第四章中详细介绍。 u t zr o e d i g 等人曾提出b r u t e f o r c e 算法【3 0 1 ，该算法将最大允许延时有效的 分配到各个融合节点上。在数据融合中，令死为上允许的延迟时间，其中 t n t ，t o 为一个任务所需的数据传输量，乞为当这个任务用数据融合来实现 石 时的数据传输量。信息由一个传感器节点& 产生，h 是该节点到s i n k 节点的跳 数。是一个传输节点产生的数据所通过路径上的节点，并距离s i n k 节点有 刀跳的距离。 算法提出用g = l t 4 t o 对融合的优劣进行评估，其中，假设数据在统一的时 间间隔丁内产生，r 被离散化为m 个小块，平均在每个小块内只有一个信息元 产生。数据在一个时间小块内到达节点的可能性取决于经过该节点进行数据 转发的节点总数瞩。m 疗为感知区域在融合延迟时间死内所产生的信息量，那么 数据在m 即个小块时间内到达节点品并发生融合时间彳疗的概率一可以由公式 p n ( a 刀) ：1 一( 型专氅) 胁来计算，其中hm n 聊。那么在传感器网络中总的融合 概率为：e ( u a 一) = a 一( p k p 0 + + ( 一1 ) ”1 兀a 个体融合节点的利润为： g = 喜a 宰万k 一喜喜c m h 等卜+ 广1 密a 嘻嘉 因此将最大融合延迟分配在各个融合节点的时间序列集合为 j x = ( m o ，m h ) n “iy ：m n 聊) 。 石 总的来说，该算法计算了在不同时间分配序列下，各个融合节点上融合事 件所发生的概率以及它的融合利润，并找出达到最大融合利润的时间分配序列， 即m，ax蹦g(x)。然而，该算法的复杂度为0(x)=c(h+m-l,mmo m h) = 端， l，je五，i力一ll - 这对于无线传感器网络的计算能力来说是不现实的【3 。因此，如何在传感器网 络能力允许的范围内，找到最优的融合延迟的分配算法仍需要进一步的研究与 探讨。 1 9 第二章相关研究的理论基础 第三节时间复杂度与n p 困难性问题相关理论 上一节提出了无损数据融合与数据传输时效性的权衡问题，具体到如何将 最大传输延迟时间合理的分配到各个节点上分布式的加以利用，并在此基础上 引出了前人开发的算法，该算法用于找出具有最大数据融合利润的时间分配序 列。然而由于该算法实现的时间复杂度为阶乘级，以现在的无线传感器网络节 点的计算能力尚无法实现。因此，本节将对时间复杂度以及第三章将提到的n p 困难性的相关理论做一个简单的介绍。 2 。3 1多项式时间复杂度 时间复杂度并不是表示一个程序解决问题需要花多少时间，而是当问题规 模扩大后，程序需要的时间增长的有多快，换句话说，对于高速处理数据的计 算机来说，处理某一个特定数据的效率不能衡量一个程序的好坏，而应该看当 这个数据的规模扩大数百倍甚至更多倍后，程序运行时间是否变化了更多，例 如随着数据规模的扩大了数百倍程序运行时间慢了数百倍，或者是慢了数万倍。 若数据规模扩大很多以后，程序处理数据所需的时间始终不变，则这个程序很 易于实现，具有d ( 1 ) 的时间复杂度，也称为常数级时间复杂度；若数据规模扩 大以后，所需的程序处理时间也随之以类似速率变长，则这个程序的时间复杂 度至少为d ( 疗) ，也成为线性时间复杂度；若数据规模扩大2 0 倍，时间变慢4 0 0 倍，则属于o ( n 2 ) 的乘方级时间复杂度。另外，还存在一些穷举类的算法，所需 时间长度随着数据规模扩大成几何阶数级增长，即为a 矿) 的指数级复杂度，或 者如上一节中的b r u t e 。f o r c e 算法所属的阶乘级复杂度o ( n t ) 。 在上述复杂度中，n 代表算法处理数据的规模，则可以将其分为两级，第一 级复杂度包括d ( 1 ) ，o ( 1 0 9 ( n ) ) ，o ( n a ) ，即常数级，对数级以及乘方级时间复杂 度，第二级复杂度则包括d ( 矿) 以及o ( n t ) ，即指数级和阶乘级时间复杂度，其中 后者的时间复杂度在任何情况下都远远大于前者。第一级复杂度称为多项式级 的复杂度，其数据规模n 出现在底数的位置，而第二级复杂度则为非多项式级 的时间复杂度，其程序运行时间在数据规模较大时计算机往往不能承受。因此 在解决实际问题时，实现的算法或解决问题采用的近似算法，通常都是多项式 级的复杂度，而非多项式级的复杂度由于计算机的能力有限，在实际应用中往 往无法直接实现，除非在数据规模固定且很小的情况下。 2 0 第二章相关研究的理论基础 2 3 2n p 完全问题与n p 困难性证明 按照上一章节给出的理论说明，计算机能够实现的算法是多项式时间复杂 度的，然而在现实应用中，并非所有的问题都可以找到一个复杂度为多项式级 的算法，甚至大部分问题根本无法找到一个多项式复杂度的近似算法来。由此 引出p 问题的概念：若一个问题可以找到一个在多项式时间复杂度内解决它的 正确算法，则该问题属于p 问题。而本文涉及到的n p 问题( n o n d e t e r m i n i s t i c p o l y n o m i a l ) ，即非确定性多项式问题，并不是非p 类问题。简而言之，n p 问题 是指那些可以在多项式时间内验证一个解正确性的问题p 2 】。 很显然，一个p 问题肯定是一个n p 问题，因为如果能在多项式时间内找到 正确的解，那肯定可以在多项式时间内验证一个解的正确性。而该命题的反命 题是否正确则是一个信息学研究中的终极问题，即是否所有的n p 问题都是p 问 题。该问题已经耗费了许多科学家的大量精力，但是仍然不得其解，而在无数 前人的研究过程中，有一类特殊的n p 问题被总结出来，即n p 完全问题。 在证明一个问题是n p 完全问题时，不是要证明存在某个有效的算法，而是 要证明不太可能存在一个有效的算法。在具体介绍n p 完全问题与n p 困难问题 的证明之前，首先给出证明中需要用到的三个重要概念。 ( 1 ) 判定问题与最优化问题 很多问题都是最优化问题，其中每一种可能的解都有一个相关的结果值， 最优化问题的目标是找出一个具有最佳结果值的可行解。例如，在无权无向图 的最短路径问题中，己知的是一个无向图g 及定点u 和1 ，要找出u 到，之间的 经过最少边的一条路径。而n p 完全性不直接适合于最优化问题，但适合于判定 问题，即答案为“是 或者“否”的问题。通常情况下，可以最优化问题与判 定问题之间有着直接的联系，且可以相互状花。例如，对于上面提到的最短路 径问题来说，该问题有一个相关的判定问题，就是要给定一个整数k ，判定在该 无权无向图g 中，顶点u 和v 之间是否存在一条包含至多k 条边的路径。 因此，在证明一个最优化问题是一个n p 完全问题时，就可以利用该问题与 相关的判定问题之间的关系。这是因为，如果某个最优化问题是比较容易的， 那么其相关的判定问题也会是比较容易的，或者说，如果能够提供证据表明某 个判定问题是个很困难的问题的话，就相当于提供了证据表明其相关的最优化 问题也是很困难的问题。 2 1 第二章相关研究的理论基础 ( 2 ) 归约 在给出归约的概念之前，首先考虑一类判定问题4 ，希望在多项式时间内解 决该类问题，并称该类问题中的某一特定问题的已知条件为该类问题的一个实 例( i n s t a n c e ) 。例如，令上述的无权无向图中的最短路径问题为彳类问题，则某 一个特定的无权无向图g ，g 中的顶点u 和，以及给定的一个整数k ，则称为 该类问题的一个实例a ，该实例下的具体判定问题为，给定一个整数k 和一个无 权无向图g 以及g 中的两个顶点u 和v ，判定顶点u 和v 之间是否存在一条包 含至多k 条边的路径。在此基础上，考虑另外一类判定问题b 以及问题b 的一 个实例b ，若找到一种多项式时间复杂度的转化算法万使得任何一个问题彳的 实例a 都可以通过厂转化为问题b 的实例b ，且实例a 的答案为“是 ，当且仅 当实例b 的答案也为“是”，则称实例a 可归约为实例6 ，即问题彳可归约为问 题b 。 这里给出归约( r e d u c t i o n ) 的定义，归约指的是这样一个多项式时间复杂 度的变化法则，对判定问题么的任何实例a ，都能按照这个法则变换成判定问题 b 的实例b ，且a 的答案为“是”，当且仅当b 的答案也是“是”。 这里举例说明归约的概念。例如，h a m i l t o n 回路问题可以归约为旅行商问 题【3 3 】，变换规则为，在h a m i l t o n 回路问题的一个实例中，两点相连即两点距离 为0 ，两点不相连则令其距离为1 ，于是该实例转化为旅行商问题的一个实例， 该实例下的问题为，是否存在一条长为0 的路径，并且h a m i l t o n 回路存在，当 且仅当旅行商问题中存在长为0 的路径。很显然，归约具有传递性，若问题a 可以归约为问题b ，问题b 可以归约为问题c ，则问题彳一定可以归约为问题c 。 根据上述内容可以得出，一个问题归约为另一个问题，时间复杂度增加了， 问题的应用范围也增大了。从另一角度来讲，通过不断研究，应该可以找到一 类复杂度最高的n p 问题，所有其他的n p 问题都可以归约为该类问题，或者说， 解决了这类问题，就解决了所有的n p 问题。这类问题就是上文提到的n p 完全 问题。下面将对第一个被证明为n p 完全问题的s a t 问题进行简单介绍。 ( 3 ) s a t 问题 s a t 问题( b o o l e a n s a t i s f i a b i l i t y p r o b l e m ) 3 2 j ，也称为公式可满足性问题， 是第一个被证明为n p 完全问题的问题。s a t 问题可以描述如下： 令集合肛 x l ，x 2 ，x n 为n 个布尔变量的集合，函数攻一 瓦毋是集 合j 上的一组赋值，当= t 时，称变量x 在赋值函数f 作用下为真，否则称 第二章相关研究的理论基础 x 在赋值函数t 作用下为假。若x 是集合x 中的个变量( v a r i a b l e ) ，则称x 与 7 石为集合x 中的定量( l i t e r a l ) 。在赋值函数f 的作用下，定量x 为真，当且仅 当变量x 为真，定量1x 为真，当且仅当变量x 为假。 集合x 中的一个句子( c l a u s e ) 是集合x 中的一个定量集合，例如 x l ，7x 4 ， x 6 ，该句子代表其中定量的析取范式，即x l v lx 4 v ，故该句子是可满足的 ( s a t i s f i e d ) 当且仅当句子中所有的定量在赋值函数f 的作用下至少有一个为真， 即仅当舷1 ) = t ，t ( x 4 ) = f ，t ( x 6 ) = t 时，句子缸l ，7x 4 ，x 6 不是可满足的，其他 赋值函数下缸l ，7x 4 ，粕 均为可满足的。令c 为布尔集合x 中的一个句子集合， 则集合c 是可满足的，当且仅当存在一个赋值函数使得集合c 中的所有句子均 可满足，该赋值函数称为集合c 上的一个可满足赋值。 综上，一个给定的布尔集合x 与x 上的一个句子集合c 称为s a t 问题的一 个实例，因此一个s a t 问题实例下的具体判定问题可叙述为：给定一个布尔集 合x 与x 上的一个句子集合c ，是否存在c 上的一个可满足赋值。 这里给出n p 完全问题的具体定义，n p 完全问题是一类可由所有n p 问题 归约而来的n p 问题。证明一个问题是n p 完全问题，需要证明： 1 ) 它是一个n p 问题，即它的解容易被验证； 2 ) 一个已经存在的n p 完全问题可以归约为它。 如果两个条件全部满足，则目标问题是一个n p 完全问题，如果只满足第二 条而不一定满足第一条，则目标问题是一个n p 困难问题。 由于s a t 问题是第一个被证明的n p 完全问题，故许多问题的n p 完全性与 n p 困难性证明均由s a t 问题归约而来，本文第三章所讨论问题的n p 困难性证 明的理论基础也是由s a t 问题的归约。 第四节本章小结 本章详细介绍了本文主题无损数据融合的研究意义，并通过简单的数 学模型的建立与计算分析，初步验证了无损融合对提升数据传输性能的积极作 用，也证明了融合约束条件对平均传输开销的影响，即并非封装在一个数据包 中的信息元越多越好，同时引出了无损融合与数据传输延时的关系，并列举了 一些前人曾经提出的算法，由该算法时间上的不可实现性引出了本文的理论性 内容，时间复杂度与n p 困难性，并在此基础上对n p 完全问题与n p 困难问题 第二章相关研究的理论基础 的定义、证明等理论基础进行了简单的介绍。下一章将就基于无损数据融合的 数据传输性能优化问题的时间复杂度进行详细的建模与分析，并就其n p 困难性 给出相应的证明。 第三章基于无损数据融合的传输优化问题的复杂性分析 第三章基于无损数据融合的传输优化问题的复杂性分析 第二章通过简单的数学建模与计算，验证了无损数据融合的研究意义，本 章首先将对系统模型与目标问题进行明确的定义。 第一节系统模型 首先给出系统模型的定义。 给出一棵信息采集树t = ( y ，e ) ，其中v 和e 分别为树中节点与边的集合， v = v i i 江1 u r ，r 为该树的根节点，同时代表无线传感器网络的s i n k 节 点，加if = 1 代表网络中个传感器节点。( 协，m ) 代表e 中的一条边，该边 须满足条件：是v f 的父节点。在该树中，v ，的父节点定义为p ，。 由于在无线传感器网络中，网络具有不同的稳定性，数据传输有时会失败， 在此情况下会在发送失败的节点上重新传输该数据，因此网络传输稳定性的不 同，需要的重传次数也是不同的，传输次数也是衡量该网络性能的一个重要指 标。这里给出一个重要的定义，即e 肼r 。h ( ，) ，该参数代表从节点h 传输一个 大小为，的数据包到它的祖先节点v ，所需要的传输次数( 包括失败后的重传次数) 的期望值，而该传输所需的时间长度定义为f v t w ( ，) 。 在该树中，任何一个节点产生的信息元x 均被定义为一个四元组 ( 仇，厶，r x ，以) ，其中协为产生x 的节点i d ，厶为该信息元的大小， 为x 产生的时 刻，么为x 被传输到s i n k 节点的最晚时刻( 若超过该时刻，则该信息元对s i n k 节点来说为无效的) 。另外，& = 么一+ 妇( 厶) ) 代表x 在网络中的空闲时间。因 此，一个节点产生的信息元x 的生命周期为【r x ，么】。 第二节问题定义 第一节给出了系统模型的详细定义，本节将对本章研究的问题进行定义。 首先给出一棵信息采集树丁，该树中产生的信息元的集合胙缸) ，其次对基 于无损数据融合的传输优化问题进行如下定义： 2 5 第三章基丁= 无损数据融合的传输优化问题的复杂性分析 问题p ：给定丁与五在确保x 中每个信息元均在其丞之前传输到s i n k 节 点的前提下，是否存在一种基于无损数据融合的数据传输调度，使得将x 成功 传输到s i n k 节点所需的传输次数最小化。 问题p 给出的是一般性的w s n 中基于无损数据融合的传输性能优化问题， 在现实中，虽然不同节点所产生的信息元取决于实际应用，但是其长度往往是 相同的【2 2 】。在用于环境监测的网络与数据采集的网络中，信息元集合x 的传输 一般会采取不同的路由方式。下面对目标问题给出更加具体的定义。 问题q ：在问题p 的基础上，x 中的信息元长度均相同且每个节点产生的 信息元至多有一个包含在x 中，当多个信息元的数据包同时存在于同一个节点 时则将多个数据包进行无损融合，且无损融合操作不允许重组，即经过融合的 信息元不能再从该数据包中取出。该问题可代表监测稀有事件且监测数据固定 为温度湿度等短小等长参数的传感器网络。 第三节基于无损数据融合的传输性能优化问题的复杂度分析 第二节给出了目标问题的具体定义，本节将对问题q 的n p 困难性进行理 论证明。 问题q 的复杂度取决于数据融合的约束条件，如最大包长，信息元长度， 最多允许封装信息元个数等等。这里将k 定义为一个数据包中可以封装的信息 元的最大个数，显然k 取决于最大有效负载长度与一个信息元的大小。下面将 分别对k 3 与k = 2 的情况进行复杂度分析。 3 3 1k 3 时问题q 的复杂度分析 根据第二章中相关内容的叙述，下述分析的理论均基于将s a t 问题【3 2 j ( b o o l e a n s a t i s f i a b i l i t y p r o b l e m ) 归约为本文目标问题q 的思路。 定理1 ：当k 3 时，问题q 是一个n p 困难问题。 下面给出定理1 的详细证明。 首先，根据2 3 2 中给出的归约与n p 困难性证明的理论基础，要证明q 的 n p 困难性，需要证明s a t 的一个实例可归约为问题q 的实例，即需要给出一 个多项式变换万使得s a t 问题的实例可以通过厂变换为问题q 的实例，并且证 2 6 第三章基于无损数据融合的传输优化问题的复杂性分析 明s a t 问题的一个实例兀中存在可满足赋值，当且仅当，问题曩的实例 兀= 厂( n ) 中存在使得所有信息元平均传输次数最小化的基于无损数据融合的 数据传输调度。 给出s a t 问题的一个实例兀，该实例中包含n 个布尔变量局，疋与伪个 句子o ，g ，下面将给出一个从兀到n 的多项式时间的变换。 首先，建立一棵n + 2 个节点的树，如图3 1 所示。在该树中，每一个节点 聊对应着一个布尔型变量并，其中，_ 1 ，刀。节点1 ，是中间协调节点，节点r 是 s i n k 节点，即汇聚节点或观测者。e 掰r 卅( ，) 为d ，其中d 远大于1 ，e t x , s 的值为1 。( 这里不考虑包长度对链路稳定性及e t x 的影响。) 传输时间咖= t 2 ， t w = t 3 。该变换的时间复杂度为伙，z ) 。 图3 1 原始，舵个节点树形的建立 假设在实例兀的m 个句子中，苟一共出现过弓次，则给每个节点v j 添加2 矿3 个子节点：w ，1 ，! ：白+ ：，给节点，添加m 个子节点：，吃。树中的每一条新 边所代表的e t x 均为l 。从吩的子节点到哆的传输时间为f l ，从到，的传输 时间为t 4 。该变换的时间复杂度为o ( n m ) 。当前的树形如图3 2 所示。 图3 2k 3 时s a t 问题到问题q 的归约 2 7 第三章基于无损数据融合的传输优化问题的复杂性分析 在建立了上面的树形结构之后，下面对其中的信息元及其生命周期进行定 义。对于每一棵根为v ，的子树，定义2 夸1 个信息元。若x 变量在g 句子中为原 值，则创建生命周期为【，；7 ，彰】= 【( 3 f + 1 ) ( 刀+ 1 ) + _ ，( 3 f + 2 ) ( ，z + 1 ) + ，+ f l + f 2 + 1 3 】的信 息元x ，若变量在c f 句子中为取非的值，则创建信息元叫，其生命周期为 1 7 ，d 】_ 【3 i ( n + 1 ) + j ，( 3 f + 1 ) ( 刀+ 1 ) + + f l + ，2 + t 3 】。由于乃变量并非在所有句子中 均出现，故令i 1 ，考虑到每个传感器节点只生成一个信息元， 因而由节点以生成的信息元，铲l ，2 妒1 ，将在生成后立刻被发送至父节点巧， 并在从”发送到1 ，之前找寻与其他信息元融合的机会。根据对生命周期的定义与 分配，在这2 计1 个信息元中，至多有两个连续的信息元可以在节点上被封装 到一起，其中，第一个信息元由以生成并在以一( t e + t 3 ) 时刻离开节点吩，第二 个信息元由节点略l 生成并于时刻略l + t l 离开节点吁。因此，节点吩会将从子节 点发来的2 ”1 个信息元封装成至少铲1 个包，其中岛个包是含有两个信息元的。 对于每个2 岛+ 1 个信息元序列来说，信息元蕊i ；与o x o 之间，必有一个为单独到 达并离开父节点v j ，若为前者，则其到达与离开吁的时刻为，+ f j ，若为后者，则 其到达并离开h 的时刻为3 ( ，时1 ) 仰+ 1 ) 可竹，。因此，上述信息元的传输次数为 r x 2 t o = 各2 匆+ 1 ) + 备( 匆+ 1 ) p + 1 ) 】。 另外，对于每一个2 足卜1 个信息元的序列来说，还有2 刀个信息元为其首尾 节点与呓岛+ 2 所分配的信息元磊与乏白+ 2 ，产1 ，聆，根据对其生命周期的定义 与分配，所有这2 托个信息元均在生成后立刻被发往其父节点，且不能和上面提 到的含有两个信息元的包再进行封装。因而，对于一个给定的，其首尾两个信 息元只能和信息元训与嚷中单独到达吁的信息元融合，或者训于产以时刻 到达并离开崎，则不与酬封装到一起，如图3 4 所示，或者锻磊于时刻 3 沏+ 1 ) ( 刀+ 1 ) 垆f ，到达并离开吁，则z 岛+ 2 与嚷封装到一起，如图3 5 所示。因 2 9 第二章基于无损数据融合的传输优化问题的复杂性分析 此，传输这些信息元的传输次数为碥= 2 n + n ( d + 1 ) 。 z 0 j ： z j l 。z 挖。五粥。 。x i k r 、一l 。i_i一 z 2 k j 2 j 8 x i 3 j 曼叠缝鼙 勰l 。 一墼照、 。 一j鳓碰一、o 一 一 3 ( 肘1 ) ( 肘1 ) + t l + t 2 + t 3 图3 4k - 3 时问题q 的最优无损融合算法一 3 ( 肘1 ) ( 卅1 ) + 芒1 + t 2 + t 3 图3 5k - - - 3 时问题q 的最优无损融合算法二 因此在该融合算法下，所有信息元的最小传输次数为v x , o + 碥+ 碥，即 刀( d + 1 ) + 1 + ? ：l ( 2 可+ 1 ) + n ，= l ( 锣+ 1 ) ( d + 1 ) 】+ 2 疗+ ，2 ( d + 1 ) 。 证明2 ：由证明1 中内容可得，在该融合算法下，或者靠与酬封装到一起， 或者乏白+ 2 与嘣封装到一起。若为前者，则每个信息元x 刍与积二融合，t = l ，磅， 并且离开吁发往1 ，的时刻为d j - ( t 2 + t 3 ) 。同理，若为后者，则每个信息元x 二与 嘭一l 融合，t = l ，弓，并且离开吁发往1 ，的时刻为形+ n 。 经过上述证明，由推论1 ，2 可得出推论3 ：在实例兀中，最小传输次数 蕊l = t a s o + m ，当且仅当，s a t 问题的实例兀中存在可满足赋值。 证明3 ：首先证明其充分性。 给定一个s a t 问题实例的可满足赋值，则相应的q 问题的最优融合算法则 衍生如下： 3 0 第三章基于无损数据融合的传输优化问题的复杂性分析 在该可满足赋值中，若逻辑变量石为真，则所有信息元从其源节点发往v j 的时刻为，从聊发往节点 ，的时刻为+ t l ；若逻辑变量苒为假，则所有信 息元x ? 从其源节点发往v ，的时刻为，从巧发往节点v 的时刻为酬一t 2 一t 3 。类 似的，由v ? 生成的信息元勿，i = 1 ，m ，不能在其源节点上进行融合，因而每个 信息元勿发送到达节点，的时刻为( 3 f + 1 ) ( 疗+ 1 ) + ，+ 幻矿幻= ( 3 升1 ) ( 万+ 1 ) + f ，+ 幻，乙在 节点，上等待的空闲时间为 ( 3 升1 ) ( ，z + 1 ) + ，+ 勿，( 3 f + 2 ) q + 1 ) + 力+ 翻。 若逻辑变量为真使得句子c ，为真值，则信息元x 到达节点v 的时刻为 ( 3 f + 1 ) ( 疗+ 1 ) + f ，+ 幻呵【( 3 f + 1 ) ( 肿1 ) + f j + 幻，( 3 i + 2 ) ( n + 1 ) + f ，+ 纠，因而乙可与任何含有 z 的数据包封装在一起。类似的，若逻辑变量西为假使得句子g 可满足，则同 理可证勿可与任何含有x 的数据包封装在一起。图3 6 与图3 7 给出了从一个 s a t 问题的实例得到最优融合算法的示例。 a x jx h pa x jx i 一z a x x + d z 姆 图3 6k 3 时由s a t 问题的实例转化为最优无损融合算法的示例一 x a x jx a x jz x a x pz 炮 - 同 1 。_ j 图3 7k 3 时由s a t 问题的实例转化为最优无损融合算法的示例二 在该算法下，所有数据包至多包含3 个信息元，满足融合约束条件，在句 子g 被骂所满足的情况下，每个信息元勿，i = 1 ，所，可以在节点，上与一个包 3 1 第二章基于无损数据融合的传输优化问题的复杂性分析 含x ? 的数据包进行融合，因此最小的传输次数需要加上传输此m 个信息元至 s i n k 节点所需的传输次数，即m ，故最终的传输次数为t x t l = t x t o + m ，充分性 得证。 接下来证明其必要性。 若找到一个最优的无损融合算法，并存在最小的传输次数t x t l ，则对一个特 定的，值，每个信息元勿与一个含有x ，的数据包封装在一起。 若x ? 离开节点v ，的时刻为+ t l ，且勿在节点v 上被封装到一个包含信息元 x 的数据包中，则在句子g 中必为原值( 即并非取非的值) ，因为信息元 叫到达节点，的时刻( 3 f + 1 ) ( 刀+ 1 ) + 巧+ 匕呵【( 3 升1 ) ( ，z + 1 ) + 以+ 乃，( 3 汁2 ) ( ，z + 1 ) + f ，+ 纠， 而3 f ( 挖+ 1 ) 呵壁【( 3 升1 ) ( ，z + 1 ) + f ，+ 匕，( 3 升2 ) ( 玎+ 1 ) + f ，+ 纠，故若乃取非，则z f 不可能与 上述数据包融合，因此这里将石值置为真。 若x ，离开节点1 = ，的时刻为彰一( t 2 + f 3 ) ，且勿在节点1 ，上被封装到一个包含 信息元的数据包中，则在句子c f 中必为取非值， 因为 ( 3 f + 1 ) ( 胛+ 1 ) + ，+ 纠 ( 3 ，+ 1 ) ( ，z + 1 ) + “+ 匕，( 3 升2 ) ( 刀+ 1 ) + r ，+ 勿】 ， 而 ( 3 i + 2 ) ( n + 1 ) + ，+ 勿呵萑 ( 3 升1 ) ( 甩+ 1 ) + 力+ 幻，( 3 f + 2 ) ( 甩+ 1 ) + f j + 纠，故这里将髯值置为假。 因此，若找到一个最优的解决该问题的无损融合算法，则可得出一个s a t 问题实例的可满足赋值。 至此，由推论3 与多项式复杂度归约规则厂得出，问题q 在k 3 的时候是 一个n p 困难问题。 3 3 2k = 2 时问题q 的复杂度分析 当肛2 且无损融合不允许重组时，可将问题q 转化为一个区间图内的最大 权重匹配问题【4 l 】，并且在多项式时间内解决该问题。 将区间图研定义在一个数轴上的区间集合，上，其中g ，针对每个集合中的 区间有且只有一个顶点，若两个区间有互相重合的部分，则g ，中相应的顶点之 间有一条边。下面给出利用区间图的最大权重匹配解决问题的算法a ： 1 针对问题生成区间图g i ( v i , e i ) ，规则如卜： 随机选择一个节点，其在时刻白生成的信息元为q ，空闲时间为，针对该生命周期 在数轴上为q 定义一个区间，白如叮】。 对于剩余的每一个信息元p ，由节点场于时刻r p 生成，其空闲时间为勘。令作为场 和峋的共同祖先节点中距离s i n k 节点r 最远的一个祖先节点，为信息元p 定义一个区 3 2 第三章基丁二无损数据融合的传输优化问题的复杂性分析 问【r q + 抽啪一t v p v w ，r q + t v q v m t v m q + 趵】。 令集合v l 为空，为每个信息元定义一个顶点s ，并加入集合巧。 令集合历为空，若代表任意两个信息元u 和h 的两个区间有互相重合的部分，则定义 一条边( “， ) ，并加入集合毋，再为边( “，功分配一个权重c o m ( u ，乃) ，其值为 c o m ( u ，向) = e t x 枷( 1 u ) + e 尺( 办) 一e z ( 如+ 如) ，其中乙和厶为信息元u 和h 的大小。 2 用e d m o n d s ，算法【3 4 1 解决上述区间图g 的最大权重匹配问题。 3 针对匹配集合中的每条边( “，办) ，信息元u 和h 在节点v u h 上被融合在一起。而对于其他 不在匹配集合中的边，其相应的信息元将不经任何融合处理，直接发送至s i n k 节点。 定理2 ：当胙2 时，算法a 可在o ( n 3 ) 时间内解决问题q ，其中n 是该问题 中所涉及的信息元的数量。 下面给出定理2 的证明。 证明：当信息元u 和h 被封装在一起的时候，传输u 和h 到s i n k 节点所需 的传输次数为e 刀( 厶) + e 扬钮( 如) 一e t x v h r ( 1 u ) 一e t x v “, r ( 1 h ) + e t x v u h r ( 1 u + 肪) ，注 意到后三项即为边( 甜，办) 的权重，故简化后为e t x w r ( 1 u ) + e t x v h r ( 1 h ) 一c o m ( u ，办) 。 令所为区间图g 的顶点集合，m 为研的匹配集合，为m 中的顶点集合， v 2 乃一。于是m 的权重w m 定义如下： w m 。( “，厅) 吖c o m ( u ，厅) 2 ( 础m e t x v r ( 1 u ) + e t x v h r ( 1 h ) 一( e t x v u g ( 1 u ) + e t x v h r ( 1 h ) 一c o m ( u , 例 2 ( 础) m ( e t x v , , r ( 1 u ) + e t x v h r ( 1 h ) ) 一椎m ( e t x v r ( 1 u ) + e t x v h r ( 1 h ) 一c o m ( u ，办) ) 2 ，胁( e 蕊( 厶) + ，们e t x v e ( 1 0 ) 一( “， ) 肘 ( e t x w r ( 1 u ) + e t x v 脓( 1 h ) 一c o m ( u , 五) ) 】一v 矿：e t x v r ( 1 v ) 2 ，所( e t x v r ( i o 一 阢排m 【( e 蕊j r ( 1 u ) + e t x v h r ( 1 h ) - c o m ( u , 堋+ 龇e t x v r ( 1 v ) 注意到在上式中，第一项v e f i ( e t x v r ( 1 v ) 的数值是一个固定值，且 ( 枷) 肘 ( e t x , , r ( 1 u ) + e t x v h r ( 1 h ) 一c o m ( u , 办) ) 】+ v e v 2e 砑细( 知) 代表算法a 所涉 及的融合算法中的全部传输次数，这里将其定义为e t x t o 幻，。因此，e ，最小 化当且仅当最大化，也就是说，对该最大权重匹配问题的解决可以为问题q 提供最优化的解决方案。 3 3 第三章基于无损数据融合的传输优化问题的复杂性分析 令胛为上述问题中涉及的所有信息元的数量，整个算法分为三个部分。第 一部分为定义一个区间图并且将权重分配给图中的每条边，该步骤的时间复杂 度为o ( n 2 ) 。算法的第二部分为用e d m o n d s 算法【3 4 】解决区间图的最大权重匹配问 题，该步骤的时间复杂度即e d m o n d s 算法的时间复杂度为o ( n 3 ) 。第三部分为将 该优化匹配问题转化为最优融合算法，该步骤的时间复杂度为阢，z ) 。因此，整 个算法的时间复杂度为d ( ，z ? ) + o ( n 3 ) + o ( n ) - - o ( n j ) ，该复杂度为多项式复杂度。 这里需要提出的是，当肛2 且无损融合不允许重组时，本文通过对问题的 合理转化，在多项式时间复杂度内解决了该问题，然而由于a 算法是一个集中 式算法，即在数据开始传输前所有信息元如何进行融合就已确定，并没有根据 传输过程中的动态情况进行适当的分布式调度，且k = 2 的情况，即一个数据包 中最多封装两个信息元，在现实应用中具有一定的局限性，因此本章内容具有 一定的理论价值。本文将在第四章中提出一种具有实用价值的基于无损数据融 合的传输调度算法。 第四节本章小结 本章给出了基于无损数据融合的传输性能优化问题的数学模型，在此基础 上对所研究的问题给出了明确的定义，并且分别在模型中一些重要参数的不同 约束条件下，对该问题的时间复杂度进行了分析。经分析与证明得出，在数据 融合不允许重组的前提下，当数据包允许封装3 个或者3 个以上信息元的时候， 该问题为n p 困难问题，而当只允许封装两个信息元时，该问题是一个在多项式 时间复杂度内可解的问题，在此基础上，该问题被转化为一个区间图内的最大 权重匹配问题，并利用根据已有算法提出的新算法a 在o ( n j ) 时间内解决了该问 题。该算法是一个集中式的无损融合算法，即在数据开始传输前，所有信息元 如何进行融合就已确定，故该研究具有一定的理论价值，但由于其融合约束条 件的局限性，本文第四章将针对特定应用领域的一般化问题，提出一种分布式 的基于无损数据融合的传输调度算法p a c k p a c k ，该算法将在数据传输过程中动 态的做出传输层决定，以优化无损数据融合与网络传输的性能。 3 4 第四章一种基于无损数据融合的传输调度算法 第四章一种基于无损数据融合的传输调度算法 第三章给出了无损数据融合的数学模型及问题定义，并且分别在不同融合 约束条件下，对该问题的时间复杂度进行了分析。经分析与证明得出，一般情 况下，该问题是一个n p 困难问题，尚不能找到一个多项式时间内可解的算法。 于是，本章将提出一种分布式的基于无损数据融合的传输调度算法p a c k p a c k ， 该算法通过对数据传输进行适当调度，将每个节点上的数据融合利用率最大化， 并降低每个信息元需要的平均传输次数，下文中将该融合利用率称为u t i l i z a t i o n 。 第一节p a c k p a c k 算法的提出背景 根据问题的定义以及在第二章中关于平均传输开销的定义与论证，这里所 讨论的算法的最终目标是使平均传输开销彳弼= 2 x 7 么幻船，最小化，其中扬r 代表将规模为如，的数据在其生命周期内传输到s i n k 节点所需的传输次数总 和，下述基于u t i l i z a t i o n 的传输调度算法p a c k p a c k 将以平均传输开销a t c 的概 念为理论基础。 简而言之，当节点，的数据缓存内有一个新数据包p l a 时，节点，可以决定 是立刻将该数据包向父节点发送还是暂不发送而等待其他数据包的到来。如果 节点，将p k t 立刻发送出去，则p l a 中所包含的信息元将在节点，的祖先节点上 与其他信息元或数据包进行融合，以减少该祖先节点数据传输的平均传输开销。 如果节点，暂不发送p k t ，将其暂时存入本地节点的缓存中，则将有更多的新数 据包到达节点，并可能与p l e t 在本地进行融合，以减少节点，传输数据的平均传 输开销。因此，该算法的关键在于判断哪种决定能够更大程度的减少网络传输 的平均传输开销，使网络的性能更高。这里将更高的性能抽象为融合利用率 u t i l i z a t i o n ，即立即发送与暂不发送两种行为的u t i l i z a t i o n ，哪个更高则采取哪种 行为。 需要指出的是，一般来讲，立即发送与暂不发送两种行为涉及到的节点只 是本地节点以及父节点，但是若只考虑本地节点及父节点