物联网论文6593549848

1、考试科目: 物联网系统设计与集成技术 姓 名:学 号: 专 业: 基于无线网络的低能耗骨干网的研究摘要在无线传感器和自主网络中对于骨干网的研究有很多方面的应用（如：路由，路由维护，广播）。以前的算法大多基于构造一个网络使其主干网的规模最小，但是，在许多应用中，我们需要建造一个骨干网在减少骨干网大小的的同时使得建造这个骨干网花费的代价最小。在这篇文章之中，我们先介绍几种以前的方法，他们都是基于使得建造骨干网的规模较少的，但是，通过他们的方法，会使网络构造产生较大的代价。于是，我们介绍一种有效地分布算法，构造出一个有较低代价的骨干网。关键词：支配集，传感器网络，分布算法，无线自组网 1 引言近些年

2、来，无线网络和无线传感器有着广泛的应用，并且引起人们极大地关注。许多路由协议在最近又有新的发展。而最简单的路由算法就是洪泛，但是，此方法不仅浪费无线网络的资源而且减少了网络的吞吐量。避免洪泛的办法就是让每个节点只与自己的一个邻节点子集通信，或者用如因特网的网络结构，比如基于支配集的算法。对于在网络中构造支配集的有效算法在以前已经有研究。大多数算法都是在减少节点的个数，也就是减少主干网的节点个数，但是，在许多无线网络的应用之中，减少骨干网的大小是远远不够的。例如，不同的无线节点在不同的节点簇中有着不同的代价。因此，我们假设每个节点都有一类代价，而且，作为节点簇代价反应了一个节点的优先度与适应度。

3、低代价的意味着高优先度。事实上，假如我们需要主干网能耗最少，那么我们考虑的代价就是能耗消耗。假如我们需要主干网容错率高，那么我们的代价就是网络的鲁棒性，因此，在不同的代价的定义下，低代价算法也有不同的应用。最近研究中，构造的簇算法都是通过不同代价作为优先度评判标准来决定节点是否能成为节点簇，但是，他们的最终目的是减少簇的大小，而不是整个簇的代价。这里主要是有效地构造一个稀疏骨干网络，从而，使得骨干网络的代价最少，并且，在本来的无线网络之中能有一条有效的路径连接无线网络的每一个节点对。2 预备知识在这部分之中，我们给出一些在下面的叙述中会用到的定义和假设，我们假设所有在V中的传感器节点都是在二维

4、空间之中。而且，每一个节点都能接收到周围节点的信号。图是节点个数为V的图，在节点与之间有边，当且仅当，与能相互的通信。也就是说他们都在相互的通信范围之内。今后，我们都称G为连接图，让代表点u的度数，代表其的最大度，每个节点都有它在主干网中的代价，这里是由电池的电量，节点的可移动性，节点在网络中的度数所决定的。大体上，越小的说明此节点越适合这个骨干网络。每一个传感器节点可以想象为一个以它自己为中心的单位圆图，定义为UDG，当且仅当假如两点之间的距离最大为1时，我们叫此网络为同构网络。我们称在图G中能在K跳之内能达到的u的节点为u的K跳节点或为u的K跳邻居节点。并把节点定义为（包括u本身），而把K

5、跳节点所构成的图为以点所构成的导出图，记作：。S是V的子集，假如当V的每个节点在S中，或者在V中的每个节点的邻居节点都在S中，那么我们就称S是V支配集。在S的每个节点被称为支配点，不在S中的点被称为被支配点。显然，最大独立集是支配集，假如C是一个支配集，而且C导出一个连接子图，那么我们就称C是V的连接支配集（CDS），显然，CDS中的每个节点都可以互相通信，而不需依靠的节点。有最少点得支配集称为最小支配集（MDS），而在MDS中有最少点的集合为最小连接支配集（MCDS），在自组网络中，假设每个点都有花费代价为，那么，一个CDS被称做有权的连接支配集（WCDS），假如C为WCDS中总代价最小的子

6、集，那么我们就称C为最小有权连接支配集（MWCDS），在这篇文章中我们就构造了一个低代价的主干网络，而问题的实质是构造一个最小有权连接支配集。3 低代价主干网络结构算法在本部分，我们构造了一个分部算法，使其在无线自组网G中建立了一个低代价的主干网络（有权连接支配集），我们假设每一个节点都知道他的ID和所有下一跳邻居节点的代价。而这过程需要每个节点对他的邻居节点发送他的ID和节点代价来实现。我们的办法包括下面的两步：第一步找到一个无线节点集作为图的支配节点集，第二步，找到一个节点集，我们叫连接点，然后将连接点连接到支配点集中，得到最后的节点集和，并把它作为主干网。注意，以上两个步骤交错进行，我们

7、为了使问题更加简单，我们把问题进行分部讨论。3.1找支配点我们要得到一个构造支配点办法，并且使得其总的代价相对较小。方法是：第一，建造一个最大独立集（MIS）以节点的权重作为选择标准。然后，对于每一个在MIS集节点v，我们用贪婪集覆盖的方法，在v的邻居节点中找到一些节点（）使得其覆盖所有的v的一跳邻居节点。如果代价小于v的代价，那么我们就用代替v，从而减少了MIS的代价。我们的方法在算法1中，例子如图1，MIS有两个节点w和v，他们的代价都很大，节点u是，显然，和，覆盖点集选择v覆盖在节点。注意到，所以v是u的支配点，另一个点w，保持他自己为支配点，因为他覆盖点集的代价比自己的大。所以最后的支

8、配点集为.算法1 构造低代价支配集（1） 假设我们把所有节点都染色为白色（WHITE）。（2） 假如它的邻居节点中有最小的代价，那么节点u发送信息给所有的下一跳邻居节点，而节点u标记为。（3） 当节点v收到由一跳邻居节点所发来的信息，节点v就将自己标为，节点v就发送性信息给v的下一跳邻居节点。（4） 当节点w收到的信息的时候，节点w会把v从染为白色（WHITE）的节点表之中删掉。（5） 节点u记上搜集所有与他相关两跳节点的代价和ID。（6） 用贪婪算法找出最小权重覆盖集，节点u找出所有两跳节点邻居节点的子集，已包含所有的节点u的一跳节点，假如被选节点的子集代价定义为，小于u节点的代价，那么节点

9、u发送信息给下一个节点w，不然的话节点u就把自己标记为。（7） 节点w收到信息后，就标记自己为。3.2 找出连接点在第二步中在被支配集中找到一些连接点，并把被支配集连接到支配点上。连接点和支配点组成了CDS（主干网）。给出一个支配集S，让代表协调器和节点对，假如u和v之间最多相隔三跳。然后我们就自然地通过把其他节点连接在网络中的u和v上，从而形成了一个CDS网络。而我们的方法是第一：我们定义两个邻居协调器u和v，满足的条件是他们两个节点最多三跳。让定义在图G中的u和v节点上为最小代价路，代表中各个节点的总代价（包括u和v代价）：，对于每一对邻居协调器u和v，我们的方法是：（1）协调器表，k表示

10、距离节点v有k步长（2）代表从v到u用k步的最小代价。（3）：代表节点是距离节点v一跳的协调器。（4）：节点是距离节点v两跳的协调器，是它的最小代价。那么我们把方法细化得到了算法2，通过比较所有的协调器的节点，我们得到WCDS（主干网）。算法2, 低代价连接节点选择1 每一个协调器节点v发送信息给在表的一跳邻居节点，用信息，当接受节点搜到来自v的信息之后，他让协调器或者假如，更新路，假如他有最小代价路2 当协调器节点w搜到从所有一跳节点信息之后，节点w发出信息，这里是最小代价路。3. 当协调器z从邻居节点w搜到信息之后，节点让假如，更新路为假如有最小代价。4 每个协调器u都建立与其他邻居协调器

11、v的虚拟边，而边的长度就是路的最小代价。注意这里的代价并没有包括节点u和v的代价，所有的虚边形成的图就是在图中的协调器序列的代价和。5 用分布算法在中构建MST，VMST定义为MST（）6 对于每一个虚边，选择每一个和协调器e相关联的被支配点作为连接点。4 总结在本篇文章之中，介绍了一个新的算法，并得到了一个在无线自主传感器骨干网络下的网络的稀疏结构。而这个分布算法的核心是在在于找到一个有权连接支配集，并且保证在此支配集中，节点的最大度数，最小度数是个常数，在算法之中，假设节点一段时间段内是静态的。而在实际生活中，网络是高度动态的，因此在主干网的权重得到之后，主干网的动态保持也是很重要的，而下

12、面两个问题也许会使骨干网失去意义(1)网络的拓补结构不断的变化，其中包括节点移动，节点加入，节点离开，节点丢失。（2）权重变化：当权重被分配给节点通过某种法则的时候，有可能在实际之中权重值变化很频繁，诸如电池或者链接质量等等原因，因此动态更新的考虑是很用必要的。而解决那些问题，我们需要在以后的研究中去实现。参考文献1 J.Wu and H.Li,”A Dominating-Set-Based Routing Scheme in A Hoc Wireless Networks,”Telecomm.SystemsJ., vol.3,pp.63-84,2001.2 Yu Wang and Weizhao W