计算机网络路由算法以及LS算法

姓名：卢佳毅

学号:23320122203951

实验五

一、实验内容

1、基础部分（6分）

对于给定的网络拓扑图（给定路由器之间的距离/代价），通过DV算法实现路由表的建立过程，具体要求见本PPT 15-17页，可提前准备，必须当场完成。

2.对于给定的网络拓扑图，通过LS算法实现路由表的建立过程。（5分）

二、实验过程

1.DV算法

#include "stdio.h"

#include "stdlib.h"

#define MAX 30000

int flag=0,n;

int Arraya[100][100];

int Arrayb[100][100],next[100][100];

int BeginningPath()//说明初始化的路由连接信息

{

int i,j,t;

printf("请输入节点的个数：");

scanf("%d",&n);//一共有n个节点

for(i=0;i

{

for(j=i+1;j

{

printf("从第%d个节点到第%d个节点的费用：",i,j);

scanf("%d",&t);

if(t==-1) t=MAX;

Arraya[j][i]=t;

Arraya[i][j]=t;

next[i][j]=j;

next[j][i]=i;

}

Arraya[i][i]=0;

}

printf("\n\n在交换路由之前: \n");

for(i=0;i

{

printf("\t");

for(j=0;j

{

if(Arraya[i][j]==MAX)

printf("∞");

else

printf("%d ",Arraya[i][j]);

}

printf("\n");

}

return 0;

}

int DVRound(int round){ //DV算法

int i,j,k;

flag=0;

for(i=0;i

{ //通过三个循环来判定Arraya中的数据是否需要更新

for(j=0;j

{

if(j!=i)

for(k=0;k

{

if(k!=i)

if(Arraya[i][j]>Arrayb[i][k]+Arrayb[k][j])

{

Arraya[i][j]=Arrayb[i][k]+Arrayb[k][j];

Arraya[j][i]=Arraya[i][j];

next[i][j]=k;

next[j][i]=j;

flag=1;

/*如果数据发生了改变，那么flag数据就会改变，输出就不是最后一轮*/

}

}

}

}

if(!flag){ //数据始终没有改变，即达到了最后一轮输出printf("交换完信息网络的最短路由费用情况:\n");

for(i =0;i

{

printf("\t");

for(j=0;j

{

if(Arraya[i][j]==-1) printf("∞");

else printf("%d ",Arraya[i][j]);

}

printf("\n");

}

return -1;

//最后一轮输出已经结束，退出程序

}

else{

printf("第%d次交换路由的情况:\n",round);

for(i=0;i

{

printf("\t");

for(j=0;j

{

if(Arraya[i][j]==MAX)

printf("∞");

else

printf("%d ",Arraya[i][j]);

}

printf("\n");

}

for(i=0;i

{

printf("r%d next cost\n",i);

for(j=0;j

{

if(j!=i)

printf("r%d %d %d\n",j,next[i][j],Arraya[i][j]);

}

}

}

return 0;

}

int main(){

int i,j;

int round = 1;

BeginningPath();

while(1)

{

for(i=0;i

for(j=0;j

Arrayb[i][j]=Arraya[i][j];

if(DVRound(round)==-1) break;

round+=1;

}

printf("请输入要查看的路由：");

scanf("%d",&i);

printf("r%d next cost\n",i);

for(j=0;j

{

if(j!=i)

printf("r%d %d %d\n",j,next[i][j],Arraya[i][j]);

}

return 0;

}

2.LS算法

#include "stdio.h"

#include"stdlib.h"

#define MAX 30000

int n;

int Arraya[100][100];

int BeginningPath()//说明初始化的路由连接信息

{

int i,j,t;

printf("请输入节点的个数：");

scanf("%d",&n);//一共有n个节点

for(i=0;i

{

for(j=i+1;j

{

printf("从第%d个节点到第%d个节点的费用：",i,j);

scanf("%d",&t);

if(t==-1) t=40000;

Arraya[j][i]=t;

Arraya[i][j]=t;

}

Arraya[i][i]=0;

}

printf("\n\n在交换路由之前: \n");

for(i=0;i

{

printf("\t");

for(j=0;j

{

if(Arraya[i][j]==40000)

printf("∞");

else

printf("%d ",Arraya[i][j]);

}

printf("\n");

}

return 0;

}

void Dijkstra(int s)

{

int flag[100],d[100]={0},next[100]={0};

int i,j,k,min;

for(i=0;i

{

d[i]=Arraya[s][i];

flag[i]=0;

next[i]=i;

}

flag[s]=1;

for(i=0;i

{

min=MAX;

for(j=0;j

if(d[j]

{

min=d[j];

k=j;

}

flag[k]=1;//标志是否放入集合

for(j=0;j<=n;j++)//松弛邻边

if(d[j]>Arraya[k][j]+d[k]&&flag[j]==0)

{

d[j]=Arraya[k][j]+d[k];

next[j]=next[k];

}

}

printf("r%d next cost\n",s);

for(i=0;i

{

if(i==s)

continue;

printf("%d : %d %d\n",i,next[i],d[i]);

}

}

int main()

{

int i;

BeginningPath();

for(i=0;i

Dijkstra(i);

return 0;

}

三、实验结果

四、实验心得

经过这次实验，熟悉了路由器交换的原理，对课本上的知识有了更深的理解。

路由算法分类

路由算法及分类 路由算法及分类： 1、非自适应算法，静态路由算法 不能根据网络流量和拓扑结构的变化更新路由表，使用静态路由表，也称为固定式路由选择算法。 特点：简单，开销少；灵活性差。 2、自适应算法，动态路由算法 可根据网络流量和拓扑结构的变化更新路由表。 特点：开销大；健壮性和灵活性好。 3、最优化原则（optimality principle） 如果路由器J 在路由器I 到K 的最优路由上，那么从J 到K 的最优路由会落在同一路由上。 4、汇集树（sink tree） 从所有的源结点到一个给定的目的结点的最优路由的集合形成了一个以目的结点为根的树，称为汇集树； 路由算法的目的是找出并使用汇集树。 几种典型的路由选择算法： 1、最短路径路由算法（Shortest Path Routing） 1）基本思想 构建子网的拓扑图，图中的每个结点代表一个路由器，每条弧代表一条通信线路。为了选择两个路由器间的路由，算法在图中找出最短路径。

2）测量路径长度的方法 结点数量 地理距离 传输延迟 距离、信道带宽等参数的加权函数 3）Dijkstra算法 每个结点用从源结点沿已知最佳路径到本结点的距离来标注，标注分为临时性标注和永久性标注； 初始时，所有结点都为临时性标注，标注为无穷大； 将源结点标注为0，且为永久性标注，并令其为工作结点； 检查与工作结点相邻的临时性结点，若该结点到工作结点的距离与工作结点的标注之和小于该结点的标注，则用新计算得到的和重新标注该结点； 在整个图中查找具有最小值的临时性标注结点，将其变为永久性结点，并成为下一轮检查的工作结点； 重复第四、五步，直到目的结点成为工作结点； 2、洪泛及选择洪泛算法 1）洪泛算法（Flooding） 属于静态路由算法 a)基本思想 把收到的每一个包，向除了该包到来的线路外的所有输出线路发送。

无线传感器网络分簇路由协议

ＩＳＳＮ１０００．９８２５．ＣＯＤＥＮＲＵＸＵＥＷ ＪｏｕｒｎａｌｏｆＳｏｆｔｗａｒｅ，Ｖ０１．１７，Ｎｏ．７，Ｊｕｌｙ２００６，ＰＰ．１５８８—１６００ ＤＯＩ：１０．１３６０／ｊｏｓｌ７１５８８ ＠２００６ｂｙＪｏｕｒｎａｌｏｆＳｏｆｔｗａｒｅ．Ａｌｌｒｉｇｈｔｓｒｅｓｅｒｖｅｄ． 无线传感器网络分簇路由协议水 沈波＋，张世永，钟亦平 （复旦大学计算机与信息技术系，上海２００４３３） Ｃｌｕｓｔｅｒ－ＢａｓｅｄＲｏｕｔｉｎｇＰｒｏｔｏｃｏｌｓｆｏｒ ＷｉｒｅｌｅｓｓＳｅｎｓｏｒＮｅｔｗｏｒｋｓ ＳＨＥＮＢｏ＋，ＺＨＡＮＧＳｈｉ—Ｙｏｎｇ，ＺＨＯＮＧＹｉ—Ｐｉｎｇ （ＤｅｐａｒｔｍｅｎｔｏｆＣｏｍｐｕｔｉｎｇａｎｄＩｎｆｏｒｍａｔｉｏｎＴｅｃｈｎｏｌｏｇｙ，ＦｕｄａｎＵｎｉｖｅｒｓｉｔｙ，Ｓｈａｎｇｈａｉ２００４３３，Ｃｈｉｎａ） ＋Ｃｏｒｒｅｓｐｏｎｄｉｎｇａｕｔｈｏｒ：Ｐｈｎ：＋８６—２１—６５６４３２３５，Ｅ—ｍａｉｌ：０４２０２１１６５＠ｆｕｄａｎ．ｅｄｕ．ｃａ，ｈｔｔｐ：／／ｗｗｗ．ｆｕｄａｎ．ｅｄｕ．ｃａ Ｅ－ｍａｉｌ：ｊｏｓ＠ｉｓｃａｓ．ａｃ．ｃｎｈｔｔｐ：／／ｗｗｗ．ｊｏｓ．ｏｒｇ．ｃａＴ乩，Ｆａｘ：＋８６．１０—６２５６２５６３ ＳｈｅｎＢ，ＺｈａｎｇＳＹ，ＺｈｏｎｇＹＰ．Ｃｌｕｓｔｅｒ－Ｂａｓｅｄｒｏｕｔｉｎｇｐｒｏｔｏｃｏｌｓｆｏｒｗｉｒｅｌｅｓｓｓｅｎｓｏｒｎｅｔｗｏｒｋｓ．ＪｏｕｒｎａｌｏｆＳｏｆｔｗａｒｅ，２００６，１７（７）：１５８８—１６００．ｈｔｔｐ：／／ｗｗｗ．ｊｏｓ．ｏｒｇ．ｃｎ／１０００－９８２５／１７／１５８８．ｈｔｍ Ａｂｓｔｒａｃｔ：Ｒｏｕｔｉｎｇｔｅｃｈｎｏｌｏｇｙａｔｔｈｅｎｅｔｗｏｒｋｌａｙｅｒｉｓｐｉｖｏｔａｌｉｎｔｈｅａｒｃｈｉｔｅｃｔｕｒｅｏｆｗｉｒｅｌｅｓｓｓｅｎｓｏｒｎｅｔｗｏｒｋｓ．Ａｓａｎａｃｔｉｖｅｂｒａｎｃｈｏｆｒｏｕｔｉｎｇｔｅｃｈｎｏｌｏｇｙ，ｃｌｕｓｔｅｒ－ｂａｓｅｄｒｏｕｔｉｎｇｐｒｏｔｏｃｏｌｓｅｘｃｅｌｉｎｎｅｔｗｏｒｋｔｏｐｏｌｏｇｙｍａｎａｇｅｍｅｎｔ，ｅｎｅｒｇｙｍｉｎｉｍｉｚａｔｉｏｎ，ｄａｔａａｇｇｒｅｇａｔｉｏｎａｎｄＳＯｏｎ．Ｉｎｔｈｉｓｐａｐｅｒ，ｃｌｕｓｔｅｒ－ｂａｓｅｄｒｏｕｔｉｎｇｍｅｃｈａｎｉｓｍｓｆｏｒｗｉｒｅｌｅｓｓｓｅｎｓｏｒｎｅｔｗｏｒｋｓａｒｅａｎａｌｙｚｅｄ．Ｃｌｕｓｔｅｒｈｅａｄｓｅｌｅｃｔｉｏｎ，ｃｌｕｓｔｅｒｆｏｒｍａｔｉｏｎａｎｄｄａｔａｔｒａｎｓｍｉｓｓｉｏｎａｒｅｔｈｒｅｅｋｅｙｔｅｃｈｎｉｑｕｅｓｉｎｃｌｕｓｔｅｒ－ｂａｓｅｄｒｏｕｔｉｎｇｐｒｏｔｏｃｏｌｓ．Ａｓｖｉｅｗｅｄｆｒｏｍｔｈｅｔｈｒｅｅｔｅｃｈｎｉｑｕｅｓ，ｒｅｃｅｎｔｒｅｐｒｅｓｅｎｔａｔｉｖｅｃｌｕｓｔｅｒ－ｂａｓｅｄｒｏｕｔｉｎｇｐｒｏｔｏｃｏｌｓａｒｅｐｒｅｓｅｎｔｅｄ，ａｎｄｔｈｅｉｒｃｈａｒａｃｔｅｒｉｓｔｉｃｓ ａｎｄａｐｐｌｉｃａｔｉｏｎａｒｅａｓａｒｅｃｏｍｐａｒｅｄ．Ｆｉｎａｌｌｙ，ｔｈｅｆｕｔｕｒｅｒｅｓｅａｒｃｈｉｓｓｕｅｓｉｎｔｈｉｓａｒｅａａｒｅｐｏｉｎｔｅｄｏｕｔ． Ｋｅｙｗｏｒｄｓ：ｗｉｒｅｌｅｓｓｓｅｎｓｏｒｎｅｔｗｏｒｋ；ｃｌｕｓｔｅｒ－ｂａｓｅｄｒｏｕｔｉｎｇｐｒｏｔｏｃｏｌ；ｃｌｕｓｔｅｒ；ｃｌｕｓｔｅｒｈｅａｄ 摘要：在无线传感器网络体系结构中，网络层的路由技术至关重要．分簇路由具有拓扑管理方便、能量利用高效、数据融合简单等优点，成为当前重点研究的路由技术．分析了无线传感器网络分簇路由机制，着重从簇头的产生、簇的形成和簇的路由角度系统地描述了当前典型的分簇路由算法，并比较和分析了这些算法的特点和适用情况．最后结合该领域当前研究现状，指出分簇路由算法未来的研究重点． 关键词：无线传感器网络；分簇路由协议；簇；簇头 中图法分类号：ＴＰ３９３文献标识码：Ａ 作为一种新的信息获取方式和处理模式，无线传感器网络（ｗｉｒｅｌｅｓｓｓｅｎｓｏｒｎｅｔｗｏｒｋ，简称ＷＳＮ）Ⅲ目前已成为国内外备受关注的研究热点． 作为一种典型的普适计算（ｐｅｒｖａｓｉｖｅｃｏｍｐｕｔｉｎｇ）应用，ＷＳＮ通过大量部署在监测区域内的传感器节点，采集网络覆盖区域内感知对象的信息，通过多跳的无线通信方式，将收集、处理后的信息提供给终端用户．ＷＳＮ不需要固定的网络支持，具有快速展开、抗毁性强等特点，可广泛应用于军事侦察、环境监测、医疗监护、农业养殖和其他商业领域，以及空间探索和灾难抢险等特殊领域【２，３】． ?Ｒｅｃｅｉｖｅｄ２００５—１２—２０；Ａｃｃｅｐｔｅｄ２００６—０２—２３

基于粒子群优化的非均匀分簇路由算法【精品文档】(完整版)

基于粒子群优化的非均匀分簇路由算法 摘要:为了解决无线传感器网络分簇路由算法中存在的“热区”问题和簇头选取问题，设计了一种自适应粒子群优化的非均匀分簇路由算法。首先通过候选节点与汇聚节点之间的距离计算竞争半径并构造出大小不等的多个簇，然后根据簇规模引入优化的粒子群算法，评价节点剩余能量和节点之间的距离等因素选取最终簇头，以剩余能量较多的簇头作为下一跳，形成以汇聚节点为根节点的多跳路由。仿真结果表明，与leach算法和eeuc算法相比，所 提算法网络生存期分别延长了34%和16%,平均能量消耗分别减少了22%和12%，有效地减少了网络节点的能量消耗。 关键词:无线传感器网络；非均匀分簇路由算法；粒子群优化算法；能量消耗；生存期 中图分类号: tp393.07 文献标志码:a abstract: to deal with the “hot area” problem and cluster heads selection in clustering routing algorithm of wireless sensor network (wsn), the paper designed an uneven clustering routing algorithm based on adaptive particle swarm optimization (pso). firstly, according to the distance between candidate nodes and sink node, the competitive radius was calculated and clusters of various sizes were constructed. then this paper introduced the pso according to the cluster size. the pso was used to select the final cluster heads by

最小生成树非均匀分簇路由算法

基于最小生成树的非均匀分簇路由算法 摘要:发现现有的针对非均匀分簇路由算法没有充分考虑簇首 与基站之间最优路径选择,而导致传输路径上的能量消耗不均衡的问题。为了更好地均衡传输路径上节点能量的消耗,提出了基于最小生成树的非均匀分簇的路由算法。该算法利用节点剩余能量和节点到基站的距离选举簇首,然后通过建立最小生成树搜寻最优传输路径,这样可以减少传输路径上的能量消耗,有效地解决能耗不均 衡问题。理论分析和实验结果均表明,该算法无论在存活节点个数还是在能量消耗上都明显优于eeuc算法和ebca。 关键词: 簇首;非均匀分簇;不均衡;剩余能量;最小生成树 uneven clustering routing algorithm based on minimum spanning tree zhang ming cai*, xue an rong, wang wei ( school of computer science and telecommunication engineering, jiangsu university, zhenjiang jiangsu 212013, china ) abstract:

the existing uneven clustering routing algorithms do not consider the optimal path selection between cluster heads and base station, which leads to unbalanced energy consumption. in order to balance energy consumption of transmission paths, this paper proposed an uneven clustering routing algorithm based on minimum spanning tree. the algorithm utilized residual energy of nodes and the distance between nodes and base station to select cluster heads, and then generated minimum spanning tree to search the optimal transmission paths, which reduced energy consumption on the transmission paths and effectively solved unbalanced energy consumption. the theoretical analysis and experimental results show that the algorithm is better than the existing energy efficient uneven clustering (eeuc) and energy balancing clustering algorithm (ebca) in terms of the number of live nodes and energy consumption. key words: cluster head; uneven clustering; unbalanced; residual energy; minimum spanning tree 0 引言 无线传感器网络(wireless sensor network, wsn)作为新兴的网

基于LEACH的无线传感器网络分簇路由算法

总第246期2010年第4期 计算机与数字工程 Computer&Digital Engineering Vol.38No.4 49 　 基于L EACH的无线传感器网络分簇路由算法3 白凤娥　牟汇慧　姜晓荣 (太原理工大学计算机与软件学院　太原　030024) 摘　要　路由协议是无线传感器网络的重要组成部分之一,而路由算法在路由协议中起着至关重要的作用。文章在L EACH算法基础上,提出一种改进的路由算法,改进后的算法采用相对固定的成簇方式,每隔一轮重新构建簇。利用图论中的prim算法,选择每轮中P ed最大的簇头作为根节点,在簇头节点之间构造树形路由,簇头之间以多跳方式将收集到的数据发送到根节点,然后通过根节点将整个网络收集到的数据发送到基站。仿真结果表明,与L EACH算法相比,改进算法降低了能耗,有效延长了网络生存周期。 关键词　无线传感器网络;L EACH算法;分簇;生命周期 中图分类号　TP393 L EACH2Based Clustering Routing Algorithm for Wireless Sensor Networks Bai Fe ngπe　M ou Huihui　J ia ng Xiaorong (College of Computer and Software,Taiyuan University of Technology,Taiyuan　030024) Abs t rac t　Routing protocol is an important part of wireless sensor network and the routing algorithm plays a crucial role in the routing protocol.Based on L EACH algorithm,this paper presents a novel clustering algorithm in which clusters are relatively fixed and the nodes re2organize themselves into new clusters every other round.It utilizes the Prim algorithm in the graph theory to form tree routing among cluster2head nodes,and selects the cluster2head with the largest P ed as the root node.The cluster heads send data to the root node in a multi2hop manner and the root node then sends the gathered data by the whole network to the base station.Simulation results show that compared with L EACH,the improved algorithm can re2 duce the energy consumption and prolong the lifetime of the network. Ke y Words　wireless sensor network,L EACH algorithm,clustering,lifetime Class Nu m ber　TP393 1　引言 无线传感器网络(Wireless Sensor Network,简称WSN)是监视远程环境的有力工具之一,它的基本功能是收集并返回传感器节点所在监测区域的信息。由于工作环境和自身构造的限制,传感器节点一般是电池供电,并且节点的更换和充电也较难实现。因此,降低节点能耗,延长网络生命周期是无线传感器网络传输机制的一个主要研究目标[1]。 网络数据传输离不开路由协议,路由协议对网络的整体性能有重要影响,因此,作为无线传感器网络核心技术之一的路由协议一直是研究的热点。路由算法在路由协议中起着至关重要的作用,无线传感器网络中的路由算法从网络逻辑结构角度可以分为平面路由和层次路由。层次路由算法是无线传感器网络路由算法的研究重点,其中,L EAC H 算法[2～3]是比较具有代表性的层次型路由算法。 本文在L EAC H算法的基础上,介绍一种改进的路由算法,改进算法的成簇方式相对固定,减少了构造簇的能量消耗。簇形成之后,在簇头间构造最小生成树,簇间通过多跳方式通信,降低了簇头节点之间长距离通信的能耗。 3收稿日期:2009年11月2日,修回日期:2009年12月5日 作者简介:白凤娥,女,教授,硕士生导师,研究方向:计算机控制与嵌入式系统,无线传感器网络。牟汇慧,女,硕士研究生,研究方向:嵌入式系统与无线自组网络。姜晓荣,女,硕士研究生,研究方向:嵌入式系统与无线自组网络。

计算机网络原理 距离矢量路由

计算机网络原理距离矢量路由 距离矢量路由选择（Distance Vector Routing）算法是通过每个路由器维护一张表（即一个矢量）来实现的，该表中列出了到达每一个目标地的可知的最短路径及所经过的线路，这些信息通过相邻路由器间交换信息来更新完成。我们称这张表为路由表，表中按进入子网的节点索引，每个表项包含两个部分，到达目的地最优路径所使用的出线及一个估计的距离或时间，所使用的度量可能是站段数，时间延迟，沿着路径的排队报数或其他。 距离矢量路由选择算法有时候也称为分布式Bellman-Ford路由选择算法和Ford-Fulkerson算法，它们都是根据其开发者的名字来命名的(Bellman，1957；Ford and Fulkerson，1962)。它最初用于ARPANET路由选择算法，还用于Internet和早期版本的DECnet 和Novell的IPX中，其名字为RIP。AppleTalk t Cisco路由器使用了改进型的距离矢量协议。 在距离矢量路由选择算法中，每个路由器维护了一张子网中每一个以其他路由器为索引的路由选择表，并且每个路由器对应一个表项。该表项包含两部分：为了到达该目标路由器而首选使用的输出线路，以及到达该目标路由器的时间估计值或者距离估计值。所使用的度量可能是站点数，或者是以毫秒计算的延迟，或者是沿着该路径排队的分组数目，或者其他类似的值。 假设路由器知道它到每个相邻路由器的“距离”。如果所用的度量为站点，那么该距离就为一个站点。如果所用的度量为队列长度，那么路由器只需检查每一个队列即可。如果度量值为延迟，则路由器可以直接发送一个特殊的“响应”（ECHO）分组来测出延时，接收者只对它加上时间标记后就尽快送回。

低功耗分簇路由算法LEACH的能耗分析

摘要：文章对无线传感器网络低功耗分簇路由协议的代表性算法—leach的运行机制以及性能做了详细的研究，针对该算法的分簇阶段、簇的建立阶段以及稳定的数据传输阶段的相关原理和运行情况作了深入分析。最后从正反两方面总结了leach协议的运行特性。 关键词：无线传感器网络；分簇路由算法；leach算法 中图分类号：tp393 文献标识码：a 文章编号：1006-4311（2012）33-0186-02 0 引言 1 leach协议描述 leach算法是mit的heinzelma等人设计的一种低能耗自适应集簇分层型路由算法，是为无线传感器网络量身设计的。此算法也是第一个在无线传感器网络中提出的分层次路由协议。在此之后提出的大部分层次式路由协议都是基于leach算法而来的。 1.1 leach协议运作周期 leach算法中簇的形成是分布式的，即节点在无中心控制下决定是否当选簇头。另外，簇的建立不需要在整个网络内进行通信，仅通过每个传感器节点自身的特征来决定的。 leach算法中定义了“轮”的概念，每轮又分为两个阶段：簇的建立阶段和稳定的数据通信阶段。第一阶段，节点按照某种信息自动成簇，随机产生一个簇头；第二阶段，簇内的非簇头节点把监测到的数据发送给簇头，簇头节点对集到的数据进行融合并把结果发送到远处的基站。在网络的初始化阶段，leach算法随机地选取一个传感器节点来充当簇头进行工作。 1.2 leach算法簇头选取机制在leach算法中，假设在t时刻开始第r+1轮簇头的选举，传感器节点i此时当选为簇头的概率为pi（t），簇头的节点的期望值为k，网络中的节点总数为n，确保网络中的所有节点在前n/k轮里都会当选一次簇头。则有以下两种情况：1、pi （t）=k/（n-k*（rmod（n/k）））（当ci（t）=1）；2、pi（t）=0（当ci（t）=0）。 r是网络已经工作过的轮数，ci（t）=0为i节点在最近的rmod（n/k）轮当选过簇头，反之，ci（t）=1为相同情况下节点i没有当选过簇头。所以只有节点在前r轮还没有当选过簇头才会拥有相对多的能量，那么就有可能在第r+1轮成为簇头[2]。接下来进入下一个周期。 1.3 簇的建立阶段一旦网络中的节点通过以上描述的方式被选举当做簇头节点，那么这些簇头节点必须向网络中的其他节点通知它们在当前轮中充当簇头的角色。为此，每个簇头节点需要以csma的方式广播一个消息并遵循mac协议[3]。消息一般包含了本身的id号和一个辨认此消息为公告的头文件，并且这个消息必须到达网络中的所有节点。leach算法中的簇头节点扮演了协调本簇数据传输的控制中心的作用。簇头节点建立一个tdma表，并且将此表发送到簇内各成员节点。当所有节点接收到了tdma表的时隙分配情况之后，簇的建立就完成了，同时进入稳定的数据传输阶段。 1.4 稳定的数据传输阶段在稳定的数据传输阶段，一个簇中的所有节点在自己对应的时隙内将监测数据发送到簇头节点，在每一个回合的时间里数据的传送依靠大量的簇内节点。用分布式算法确定簇头节点保证了每轮簇的期望值为k，但是不能保证在每一轮中正好都是k 个簇。因而，在leach算法中每个簇中节点的数目具有高度的不确定性，并且簇内节点传送给簇头的数据量随着簇内节点数的不同会产生变化。 簇头节点要接受所有簇内节点发送数据，则必须保持自己的接收器一直处于工作状态。一旦簇头节点接收到了来自所有节点发送过来的数据之后，即进行数据融合，再将结果发送到基站。因此簇头对基站的数据传输将产生很高的能量消耗。 前面的讨论描述了无线传感器网络簇内的通信。mac协议和路由协议的设计要保证节点的低能量消耗和簇内节点数据传送无冲突。每个簇拥有一个独一无二的传播覆盖代码，簇内

计算机网络实验报告(路由算法、Socket编程)

计算机网络实验报告 班级： 姓名： 学号：

实验一 一．实验目的及要求 编写程序，模拟距离矢量路由算法的路由表交换过程，演示交换后的路由表的变化。 二．实验原理 距离矢量路由算法是这样工作的：每个路由器维护一张路由表（即一个矢量），它以网络中的每个路由器为索引，表中列出了当前已知的路由器到 每个目标路由器的最佳距离，以及所使用的线路。通过在邻居之间相互交换 信息，路由器不断地更新他们的内部路由表。 举例来说，假定使用延迟作为“距离”的度量标准，并且该路由器发送一个列表，其中包含了他到每一个目标路由器的延时估计值；同时，他也从 每个邻居路由器接收到一个类似的列表。假设一个路由器接收到来自邻居x 的一个列表，其中x（i）表示x估计的到达路由器i所需要的时间。如果该 路由器知道他到x的延时为m毫秒，那么他也知道在x（i）+m毫秒之间内经 过x可以到达路由器i。一个路由器针对每个邻居都执行这样的计算，就可 以发现最佳的估计值，然后在新的路由器表中使用这个最佳的估计值以及对 应的输出路线。 三．源程序： #include "stdio.h" #include "stdlib.h" #include "malloc.h" #include "graphics.h" #include "dos.h" #define VERNUM 7 typedef struct { int dis; int flag; int flag2; }RoutNode; char tmp[10]; RoutNode data[VERNUM][VERNUM]; void welcome(); void InitRoutData(FILE* pfile); void PrintRoutData(); void SendInf(int recv, int send); void Exchange(); int main() { int start, end, i, j, m, n; FILE *pfile;

计算机网络复习题

名词解释： 1、ICMP： ICMP是Internet控制消息协议。它是TCP/IP协议族的一个子协议，用于在IP主机、路由器之间传递控制消息。控制消息是指网络通不通、主机是否可达、路由是否可用等网络本身的消息。这些控制消息虽然并不传输用户数据，但是对于用户数据的传递起着重要的作用。ICMP协议和IP 协议一样工作在网络层。但是ICMP本身是作为IP协议的数据内部被传输的。 2、CSMA/CD协议:载波监听多点接入碰撞检测，用于以太网上多点接入技术,每个站检测信道是否空闲，不空闲则等待，空闲则发送数据，如果碰撞使用二进制指数退避算法等待一段时间在发送。 3、GBN: 回退N步的协议，是可靠数据传输中滑动窗口协议的一种，发送端通过发送窗口限制发送的数据数量，当收到某个数据的确认时，发送窗口向后移动一个单位，，接收端只接受按序到达的正确的数据，其它的丢弃，并发上一个正确到达的分组的序号的确认或当前分组的否认。 4、SR: 选择性重传SR协议，即发送方某个分组出错或丢失只重传该分组。增加方收到窗口，若收到的分组在接受窗口内且乱序，缓存该分组，等到分组按序后一起提交，接受窗口的大小一般等于发送方发送窗口的大小，且窗口的大小必须小于或等于序号大小的一半。 5、NAT:网路地址转换： 用于IP地址的转换。它解决了多个用户使用一个公网IP上网的问题，缓解了IP地址的危机；实现了内部IP地址隐藏及服务器负载均衡。它分为静态NAT，动态NAT，和端口NAT三类。 6、URL: 统一资源定位符，是用于完整地描述Internet上网页和其他资源的地址的一种标识方法，　URL由三部分组成：协议类型，主机名和路径及文件名。它是为了能够使客户端程序查询不同的信息资源时有统一访问方法而定义的一种地址标识方法。在Internet上所有资源都有一个独一无二的URL地址 7、HTTP: 超文本传输协议。用于定义Web页面在网络上的交互方式的应用层

基于节点度和距离的WSN分簇路由算法

———————————— 作者简介作者简介：：李 辉(1976－)，男，副教授，主研方向：无线传感器网络；刘书吉，硕士研究生。 收稿日期收稿日期：：2013-03-04 修回日期修回日期：：2013-04-18 E-mail ：li20042007@https://www.wendangku.net/doc/8f12372399.html, 基于节点度和距离的WSN 分簇路由算法 李 辉，刘书吉 (河南理工大学电气工程与自动化学院，河南 焦作454000) 摘 要：针对无线传感器网络(WSN)中节点的负载均衡问题，提出一种基于节点度和距离的WSN 非均匀分簇路由算法。该算法在首轮成簇时采用了定时机制的簇头竞争方案，定时的长短取决于节点本身的节点度和距离基站的距离，且节点根据不同的竞争半径形成不同的簇。在首轮成簇结束后，簇的结构不再发生变化，而簇头的轮换则根据簇内节点的剩余能量和距离本簇质心的通信代价在簇内进行动态轮换。采用簇间多跳路由，根据节点的剩余能量、距离基站的距离、节点间通信代价和节点的转发热度来选择中继节点。仿真结果表明，该算法的网络生命周期与LEACH 协议相比延长了2倍以上，与EEUC 协议相比延长了13.97%，且均衡了网络的能量消耗。 关键词关键词：：无线传感器网络；非均匀分簇；节点度；距离；转发热度；动态轮换 Clustering Routing Algorithm Based on Node Degree and Distance for Wireless Sensor Networks LI Hui, LIU Shu-ji (School of Electrical Engineering and Automation, Henan Polytechnic University, Jiaozuo 454000, China) 【Abstract 】Aiming at the problem of unnecessary energy consumption caused by periodic clustering and the load balance problem in the Wireless Sensor Networks(WSN), an Unequal Clustering routing algorithm based on node Degree and Distance for WSN(UCDD) is proposed. UCDD algorithm adopts the time competitive mechanism in the first round of clustering. The length of time depends on the nodes’ node degree and the distance from the base station, and different clusters are formed according to the different radius of competition. After the first round, the clusters’ structure does not change any more. Cluster head dynamically choose next cluster head according to the residual energy and the communication costs. Inter-cluster multihop routing is used in UCDD algorithm, and the relay node is selected according to node residual energy, distance from the base station, communication cost of nodes and relay hot. Simulation results show that the algorithm can prolong the networks lifetime by more than two times compared with LEACH protocol and by 13.97% compared with EEUC protocol. Besides, it balances the energy dissipation of the networks. 【Key words 】Wireless Sensor Networks(WSN); unequal clustering; node degree; distance; relay heat; dynamic rotation DOI: 10.3969/j.issn.1000-3428.2014.03.023 计 算 机 工 程 Computer Engineering 第40卷 第3期 V ol.40 No.3 2014年3月 March 2014 ·移动互联与通信技术移动互联与通信技术·· 文章编号文章编号：：1000-3428(2014)03-0113-07 文献标识码文献标识码：：A 中图分类号中图分类号：：TP391 1 概述 无线传感器网络(Wireless Sensor Networks, WSN)是继互联网之后的又一个对人类生活产生重大影响的IT 技术[1]。由于传感器节点的能量受限，因此基于分层的路由协议备受关注。基于概率的低功耗自适应分簇协议(Low-energy Adaptive Clustering Hierarchy, LEACH)[2]是最早的分簇路由协议，几乎贯穿了后来发展的大多数分簇协议。该协议通过等概率随机循环地选择簇头以此来将整个网络的能量负载平均分配到每个传感器节点上，从而达到降低网络能量耗费、延长网络生命周期的目的[3]。LEACH 协议成簇时簇首选择方法简单，易于实现。但是，LEACH 协议的缺点也非常明显：(1)在簇头选择时没有考虑能量因素，无论节点 的剩余能量多少都有可能成为簇头，从而加速了低能量节点的死亡；(2)簇头分布不均；(3)在数据传输时采用了单跳模式数据传输，当传输相同的数据时距离基站远的簇头的节点能耗较快。文献[4]的HEED 算法在簇头选择时依据主参数能量和次参数簇内通信代价，其分簇速度更快，并且产生的簇头分布比较均匀、网络的拓扑结构也更加合理。但是在成簇时通信开销大。文献[5]提出的最小ID 分簇算法，方法简单易行。但是在成簇时需要相互交换ID 号，带来很大的能量开销，并且选择的簇头分布不太均匀。文献[6]提出的集中式分簇算法(LEACH-C)，每轮结束时将能量信息和位置信息发送给基站，由基站来选择簇头。虽然解决了簇头分布不均问题，但是每轮都要发送能量和位置信息浪费了大量的能量。文献[7]提出的基于竞争的非均匀分簇

基于社区的容迟网络路由方法_周瑞涛

收稿日期：２０１１－０６－ ２４基金项目：国家自然科学基金资助项目（６１１０１２１４ ）作者简介：周瑞涛（１９８１—），男，博士生，Ｅ－ｍａｉｌ：ｚｒｔ＠ｂｉｔ．ｅｄｕ．ｃｎ；曹元大（１９４４—），男，教授，博士生导师，Ｅ－ｍａｉｌ：ｙ ｄｃａｏ＠ｂｉｔ．ｅｄｕ．ｃｎ．第３２卷　第９期２０１２年９月 北京理工大学学报 Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｆ　Ｂｅｉｊｉｎｇ　 Ｉｎｓｔｉｔｕｔｅ　ｏｆ　ＴｅｃｈｎｏｌｏｇｙＶｏｌ．３２　Ｎｏ．９Ｓｅｐ ．２０１２基于社区的容迟网络路由方法 周瑞涛１，　曹元大１，　胡晶晶２，　朱东锋 １ （１．北京理工大学计算机学院智能信息技术实验室，北京　１０００８１；２．北京理工大学软件学院，北京　１０００８１）摘　要：提出一种基于社区的容迟网络路由方法．通过对网络节点历史运动轨迹点聚类建立其热点活动区域，把热点区域重叠度较高的节点归为同一社区．在源节点和目的节点社区中以洪泛的方式加快消息扩算和传递速度．同时，针对热点区域准确地选择中继节点，降低了冗余消息数量．模拟结果显示，该方法能够提高消息传递数量，并且大大降低系统负载率． 关键词：容迟网络（ＤＴＮ） ；聚类；社区中图分类号：ＴＰ　３９３．０３ 文献标志码：Ａ 文章编号：１００１－０６４５（２０１２）０９－０９６６－ ０５Ｃｏｍｍｕｎｉｔｙ　Ｂａｓｅｄ　Ｒｏｕｔｉｎｇ　ｉｎ　Ｄｅｌａｙ　 ａｎｄ　Ｔｏｌｅｒａｎｃｅ　ＮｅｔｗｏｒｋｓＺＨＯＵ　Ｒｕｉ－ｔａｏ１，　ＣＡＯ　Ｙｕａｎ－ｄａ１，　ＨＵ　Ｊｉｎｇ－ｊｉｎｇ２，　ＺＨＵ　Ｄｏｎｇ－ｆｅｎｇ １ （１．Ｂｅｉｊｉｎｇ　Ｌａｂｏｒａｔｏｒｙ　ｏｆ　Ｉｎｔｅｌｌｉｇｅｎｔ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｔｅｃｈｎｏｌｏｇｙ，Ｓｃｈｏｏｌ　ｏｆ　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ，Ｂｅｉｊｉｎｇ　Ｉｎｓｔｉｔｕｔｅ　ｏｆＴｅｃｈｎｏｌｏｇｙ，Ｂｅｉｊｉｎｇ　１０００８１，Ｃｈｉｎａ；２．Ｓｃｈｏｏｌ　ｏｆ　Ｓｏｆｔｗａｒｅ，Ｂｅｉｊｉｎｇ　Ｉｎｓｔｉｔｕｔｅ　ｏｆ　Ｔｅｃｈｎｏｌｏｇｙ，Ｂｅｉｊｉｎｇ　 １０００８１，Ｃｈｉｎａ）Ａｂｓｔｒａｃｔ：Ａ　ｎｅｗ　ｔｅｃｈｎｉｑｕｅ　ｆｏｒ　ｃｏｍｍｕｎｉｔｙ　ｂａｓｅｄ　ｒｏｕｔｉｎｇ　ｉｎ　ｄｅｌａｙ　ａｎｄ　ｔｏｌｅｒａｎｃｅ　ｎｅｔｗｏｒｋｓ（ＤＴＮｓ）ｉｓ　ｐｒｏｐｏｓｅｄ．Ｔｈｅ　ｈｉｓｔｏｒｙ　ｍｏｂｉｌｉｔｙ　 ｔｒａｃｋｓ　ａｒｅ　ｕｓｅｄ　ｔｏ　ｅｓｔａｂｌｉｓｈ　ｔｈｅ　ｍｏｓｔ　ｖｉｓｉｔｅｄ　ａｒｅａ　ｏｆ　ＤＴＮｎｏｄｅｓ，ｃａｌｌｅｄ　ｈｏｍｅ　ａｒｅａ，ｔｈｒｏｕｇｈ　ｃｌｕｓｔｅｒｉｎｇ．Ｔｈｅ　ｎｏｄｅｓ　ｗｈｏｓｅ　ｈｏｍｅ　ａｒｅａｓ　ｏｖｅｒｌａｐ　ｍｏｓｔ　ａｒｅｒｅｇａｒｄｅｄ　ａｓ　ｉｎ　ｔｈｅ　ｓａｍｅ　ｃｏｍｍｕｎｉｔｙ．Ｔｈｅ　ｄｅｌｉｖｅｒｙ　ｓｐｅｅｄ　ｃｏｕｌｄ　ｂｅ　ａｃｃｅｌｅｒａｔｅｄ　ｂｙ　ｆｌｏｏｄｉｎｇ　 ｎｏｄｅｓ　ｉｎｔｈｅ　ｓｏｕｒｃｅ　ａｎｄ　ｄｅｓｔｉｎａｔｉｏｎ　ｃｏｍｍｕｎｉｔｉｅｓ．Ｆｕｒｔｈｅｒｍｏｒｅ，ｔｈｅ　ｈｏｍｅ　ａｒｅａ　ｆａｃｉｌｉｔａｔｅｓ　ｔｈｅ　ｓｅｌｅｃｔｉｏｎ　ｏｆｉｎｔｅｒｍｅｄｉａｔｅ　ｎｏｄｅｓ．Ｓｉｍｕｌａｔｉｏｎ　ｒｅｓｕｌｔｓ　ｓｈｏｗ　ｔｈａｔ　ｔｈｉｓ　ｍｅｔｈｏｄ　ｃｏｕｌｄ　ｉｍｐｒｏｖｅ　ｔｈｅ　ｍｅｓｓａｇｅ　ｄｅｌｉｖｅｒｙｒａｔｅ　ａｎｄ　ａｃｈｉｅｖｅ　ｌｅｓｓ　 ｏｖｅｒｈｅａｄ．Ｋｅｙ　ｗｏｒｄｓ：ｄｅｌａｙ　ａｎｄ　ｔｏｌｅｒａｎｃｅ　ｎｅｔｗｏｒｋｓ（ＤＴＮ）；ｃｌｕｓｔｅｒ；ｃｏｍｍｕｎｉｔｙ 容迟网络体系结构用来解决受限环境下的网络通信问题［１］ ，此类环境中，由于节点的运动规律、生命周期等特性，节点间往往不存在一条永久的端到端路径，例如星际网络、传感器网络等． “存储转发”是该类网络最基本的路由方式．消息需要缓存在中继节点中等待合适的转发机会出现才被传至下一跳节点，直到成功传递．容迟网络路由技术要解决的关键问题是如何选择合适的中继节点． Ｅｐ ｉｄｅｍｉｃ［２］ 通过以洪泛方式传播消息，能够适应各种网络环境，但是往往导致非常高的网络负载；通过限制Ｅｐ ｉｄｅｍｉｃ洪泛的副本数量，其很多变体被提出来［３－ ４］；在社区模型下，ＰＲＯＰＨＥＴ［５］利用节点 间接触的历史信息预测未来的相遇概率指导路由； Ｎｅｔｗｏｒｋ　ｃｏｄｉｎｇ［６］和Ｅｒａｓｕｒｅ　ｃｏｄｉｎｇ［７］ 通过编码的 方式应对报文丢失；此外，还有基于模型［８］ 、控制节点运动［ ９］ 等方法应对各种各样的容迟网络环境．作者针对社区模型的特点，通过对节点历史运动轨迹点聚类，建立热点活动区域，进而建立社区辅助路由．在源节点社区中洪泛消息使其在产生之初迅速传播开，同样在目的节点社区中通过洪泛的方式迅速路由消息到目的节点．同时，利用节点活动的热点区域准确地选择中继节点降低消息冗余，节省网络资源．

机会网路典型路由算法

1.1机会网路典型路由算法研究 机会网络是一种节点分布稀疏、网络拓扑结构不断发生变化的间歇性通信网络。数据以多跳方式，采用“接收-携带-转发”的机制传输给目的节点，如果中间节点没有合适的可供传输的路径或节点，则无法立刻将数据转发出去，而是保存在节点缓存中，等到出现合适的传输机会之后，再将消息转发出去。而现有的有线网络和无线自组织网络中基于TCP/IP 协议的端到端路由协议已经不再适用于机会网络。因此，如何在机会网络中寻找一条时延尽可能低、消耗尽可能小、传输成功率尽可能高的路径，将消息准确传递到目的节点，是机会网络中一个极具挑战性的问题。从不同角度出发，机会网络的路由策略有不同的分类方式[27]。按照消息传输方式可分为洪泛路由策略和转发路由策略；按照路由所使用报文的份数可分为单报文路由策略和多报文路由策略；按照节点所掌握的网络拓扑信息还可分为确定性路由策略和随机性路由策略。本文按照消息传输方式不同将目前的路由协议分为如下几类：直接传输路由策略(Direct Transmission)、基于泛洪的路由策略(Flooding Based)、基于情景感知的路由策略(Context Based)、基于社区的路由策略(Community Based)、基于编码的路由策略(Coding Based)、基于预测的路由策略(Predicted Based)。 1.1.1基于副本或泛洪的路由策略 直接传输(Direct Transmission，DT)路由在运行过程中，不产生消息副本，消息一直保存在源节点缓存中，直到源节点在运动过程中遇到目的节点，才将消息转发给目的节点。DT 路由协议由于没有进行路由优化处理，也没有产生任何副本消息，因此传输时延很大。为了减少网络中消息的传输时延，研究人员提出了基于泛洪的路由协议，通过消息携带节点产生大量的消息副本，转发给每一个相遇的节点，完成消息的投递。根据网络中消息副本数量的多少，还可以将基于泛洪的路由分为两大系列：泛洪路由和限制性泛洪路由。 最简单的泛洪路由为传染病路由或称为流行性路由(Epidemic Routing)[13]。顾名思义，传染病路由中消息的分发类似于传染病病毒散发，当消息携带节点在移动过程中碰到没有携带该消息的节点时，便产生消息副本并传递给对方，然后该节点将消息存储在自身缓存中，继续转发给所遇到的其他节点，直到消息传递到目的节点或者消息的TTL 等于零。 实际的网络中，节点的缓存和能量都有限，不可能保证足够的带宽资源，Epidemic 路由的性能将急剧下降，另外大量的冗余信息将过多地消耗节点能量，

基于粒子群优化非均匀分簇路由算法

基于粒子群优化的非均匀分簇路由算法摘要:为了解决无线传感器网络分簇路由算法中存在的“热区”问题和簇头选取问题，设计了一种自适应粒子群优化的非均匀分簇路由算法。首先通过候选节点与汇聚节点之间的距离计算竞争半径并构造出大小不等的多个簇，然后根据簇规模引入优化的粒子群算法，评价节点剩余能量和节点之间的距离等因素选取最终簇头，以剩余能量较多的簇头作为下一跳，形成以汇聚节点为根节点的多跳路由。仿真结果表明，与leach算法和eeuc算法相比，所 提算法网络生存期分别延长了34%和16%,平均能量消耗分别减少了22%和12%，有效地减少了网络节点的能量消耗。 关键词:无线传感器网络；非均匀分簇路由算法；粒子群优化 算法；能量消耗；生存期 中图分类号: 文献标志码:a abstract: to deal with the “hot area” problem and cluster heads selection in clustering routing algorithm of wireless sensor network (wsn), the paper designed an uneven clustering routing algorithm based on adaptive particle swarm optimization (pso). firstly, according to the distance between candidate nodes and sink node, the competitive radius was calculated and clusters of various sizes were constructed. then this paper introduced the pso according to the cluster size. the pso was used to select the final cluster heads by