leach_mit结构图
从wireless.tcl文件中分析leach的具体流程
在wireless.tcl文件中首先初始化了很多无限仿真的配置。引用了一些外部脚本——source tcl/lib/ns-mobilenode.tcl（主要是包含移动节点类Node/MobileNode的一些otcl类函数的定义）、source tcl/lib/ns-cmutrace.tcl（trace文件的tcl脚本）、 source
tcl/mobility/$opt(rp).tcl（将几种不同的协议的具体应用的外部脚本引用，$opt(rp)是协议名称）。当一些变量初始化过后，通过
elseif { [string compare $opt(rp) "leach"] == 0} {
for {set i 0} {$i < $opt(nn) } {incr i} {
leach-create-mobile-node $i
建立我们仿真的节点，最主要的函数是leach-create-mobile-node（这个函数的定义在uamps.tcl中）
分析uamps.tcl中是如何定义节点的？？？
在uamps.tcl中初始化了bsnode的应用类型（Application/BSApp）、定义了二个能量传输模型（自由信道和多径衰落、Efriss_amp和Etwo_ray_amp）和很多参数。而真正创建节点是在函数leach-create-mobile-node中。而这个函数中调用了uamps.tcl中的sens_init，这个函数的功能是清除上一次模拟时留下的trace文件。在创建节点时候，sens_init函数调用一次。leach-create-mobile-node函数解释如下：
1、节点定义：
if {$id != $opt(nn_)} {
puts -nonewline "$id "
set node_($id) [new MobileNode/ResourceAwareNode] #将前opt(nn_)-1个点定义为一般节点
} else {
puts "($opt(nn_) == BS)"
set node_($id) [new MobileNode/ResourceAwareNode $BS_NODE] #将第
opt(nn_)个节点定义为最终的sink节点
$node_($id) label "BS"
$node_($id) label-color red
}
2、初始化能量：
if {$id != $opt(nn_)} { #如果节点的能量相等，就将所有普通节点的能量初始化为$opt(init_energy)。
# Set initial node energy.
if {$opt(eq_energy) == 1} {
$node set-energy $opt(init_energy) $opt(thresh_energy)
} else {
#set E [$rng_ uniform $opt(lower_e) $opt(upper_e)]
#set rn [$rng_ uniform 0 1]
#if {$rn < 0.1} {
# set E 200 #如果节点能量不相等，就将97 19 12 87 8 22 83 55
#} else { #34 72节点的能量定义为200，其他节点定义为2
# set E 2
#}
set high_e_nodes [list 97 19 12 87 8 22 83 55 34 72]
if {[lsearch $high_e_nodes $id] == -1} {
set E 2
} else {
set E 200
}
$node set-energy $E $opt(thresh_energy)
set initf [open "$opt(dirname)/init.energy" a]
puts $initf "$id\t$E"
close $initf
}
} else {
# Base station has an infinite amount of energy.
$node set-energy 50000 $opt(thresh_energy) #将最终sink节点的能量定义
} #为50000，就相当于无穷大。
3、配置节点的信道和跟踪文件：
# Connect the node to the channel.
$node add-interface $chan $prop $opt(ll) $opt(mac) \ #add-interface定义在ns-ranode.tcl中
$opt(ifq) $opt(ifqlen) $opt(netif) $opt(ant) \
$topo $inerrProc_ $outerrProc_ $FECProc_
# Set up the trace target.
set T [new Trace/Generic]
$T target [$ns_ set nullAgent_]
$T attach $tracefd
$T set src_ $id
$node log-target $T。
这样节点的定义就定义好了。而在leach-create-mobile-node函数中普通节点是new MobileNode/ResourceAwareNode，最终sink节点是new MobileNode/ResourceAwareNode $BS_NODE但是普通节点和一般节点它们的区别是什么？在ns-ranode.tcl文件中找到了MobileNode/ResourceAwareNode的定义。
MobileNode/ResourceAwareNode类到底是怎么定义的呢？？
在ns-ranode.tcl中能看到它的初始化函数定义：
MobileNode/ResourceAwareNode instproc init args {
global ns_ opt wantslist tracefd
$self instvar entry_point_
$self instvar rca_agent_ rca_app_ ll_ mac_ ifq_ netif_
$self instvar ResourceManager_
set bs_node [lindex $args 0] #如果是最终sink就更bs_node赋1、否则赋0
eval $self next [lreplace $args 0 0] #这是调用它的父类Node/MobileNode初始化函数，初始化一般移动节点的功能，所以我们定义的节点也含有一般节点的功能
# Set up the resource manager
set ResourceManager_ [new ResourceManager] #这一行是在节点中增加了
$ResourceManager_ Register [new Resource/NeighborResource] #ResourceManager set energy [new Resource/Energy] #Resource/NeighborResource 和
$ResourceManager_ Register $energy #Resource/Energy三个模块，实现了对节点能量的管理
# Create a new agent and attach it to the node #这也正是最终sink节点和普通节点的区别
if {$bs_node == 1} {
set agent [new Agent/BSAgent] #最终sink节点的Agent是BSAgent
} else {
set agent [new Agent/RCAgent] #普通节点是RCAgent
}
set rca_agent_ $agent
# Stick a "receive" trace object between the #接下来的代码有些看不懂先放在这
# entry point and the agent. #里，这个暂时不影响程序分析
set rcvT [cmu-trace Recv "AGT" $self] #？？？？？
$rcvT target $agent
set entry_point_ $rcvT
# Add a Log Target
set T [new Trace/Generic]
$T target [$ns_ set nullAgent_]
$T attach $tracefd
$T set src_ [$self id]
$rca_agent_ log-target $T
# Attach an application to the agent
set haslist [find_haslist [$self id]] #???
if {$bs_node == 1} {
set rca [new $opt(bsapp)] #这个也是最终节点和普通节点的区别，它们代理上
} else { #的应用不同。最终节点的应用是Application/BSApp，定义在ns-bsapp.tcl 中
set rca [new $opt(rcapp) $opt(mtype) $wantslist $haslist] #opt(rcapp)定义在
} #leach.tcl中，为Application/LEACH；opt(mtype)定义在leach.tcl中
$ns_ attach-agent $self $agent
$rca attach-agent $agent
set rca_app_ $rca
}
从以上分析我们知道了簇头和节点的定义，以及它们的一些区别。其中我们知道了一般节点的应用为Application/LEACH，最终sink节点的应用为Application/BSApp。而且它们都是otcl的类。普通节点是过Application/LEACH来进行选簇的。也是leach协议的一个重要功能。
说明一下，在leach协议的仿真中每个普通节点的mac层都有leach应用，也就是说每个普通节点都会执行ns-leach.tcl中的一些功能（即函数）。所以，分析ns-leach.tcl才能够明白leach的具体选簇功能的实现。
在ns-leach.tcl中初始化函数初始化了很多变量，这里不说。
Application/LEACH instproc start {} { #当在otcl类定义一个实例时，start函数会
[$self mac] set node_num_ [$self nodeID] #自动执行
$self decideClusterHead #决定簇头的函数
$self checkAlive #检查节点是否存活的函数
}
1、
选簇函数分析：
Application/LEACH instproc decideClusterHead {} {
global chan ns_ opt node_
$self instvar next_change_time_ round_ clusterNodes_
$self instvar now_ TDMAschedule_ beginningE_ alive_
$self instvar myADVnum_ CHheard_
set CHheard_ 0
[$self mac] set CHheard_ $CHheard_ #CHheard_ 、myADVnum_在mac层被绑定的数据
set myADVnum_ 0 #在mac-sensor.h中的定义
#int CHheard_; // Number of other CH ADVs heard
#int myADVnum_; // Position of node's ADV among all ADVs
[$self mac] set myADVnum_ $ #具体做用没有分析明白？
# Check the alive status of the node. If the node has run out of
# energy, it no longer functions in the network.
set ISalive [[[$self node] set netif_(0)] set alive_] #从网络接口netif中查看当前节点状况
if {$alive_ == 1 && $ISalive == 0} { #具体调用过程还不清楚？
puts "Node [$self nodeID] is DEAD!!!! Energy = [[$self getER] query]"
$chan removeif [[$self node] set netif_(0)] #如果一个当前是存活的（alive=1）但是能
set alive_ 0 #量消耗完，就从信道中将它移出
set opt(nn_) [expr $opt(nn_) - 1]
}
if {$alive_ == 0} {return}
set now_ [$ns_ now]
set nodeID [$self nodeID]
set beginningE_ [[$self getER] query] #获取当前节点的能量（自己认为的？？）
$self setCode 0 #对节点mac层的code_进行设置
$self WakeUp #对节点处于空闲和休眠状态进行能量消耗的计算
set tot_rounds [expr int([expr $opt(nn_) / $opt(num_clusters)])]
if {$round_ >= $tot_rounds} {
set round_ 0
}
if {$opt(eq_energy) == 1} {
#
# Pi(t) = k / (N - k mod(r,N/k))
# where k is the expected number of clusters per round
# N is the total number of sensor nodes in the network
# and r is the number of rounds that have already passed.
#
set nn $opt(nn_)
if {[expr $nn - $opt(num_clusters) * $round_] < 1} {
set thresh 1
} else {
set thresh [expr double($opt(num_clusters)) / \
[expr $nn - $opt(num_clusters) * $round_]]
# Whenever round_ is 0, all nodes are eligible to be cluster-head.
if {$round_ == 0} {
$self hasnotbeenClusterHead
}
}
# If node has been cluster-head in this group of rounds, it will not
# act as a cluster-head for this round.
if {[$self hasbeenClusterHead?]} {
set thresh 0
}
} else {
#
# Pi(t) = Ei(t) / Etotal(t) * k
# where k is the expected number of clusters per round,
# Ei(t) is the node's current energy, and Etotal(t) is the total
# energy from all nodes in the network.
#
set Etotal 0
# Note! In a real network, would need a routing protocol to get this
# information. Alternatively, each node could estimate Etotal(t) from # the energy of nodes in its cluster.
for {set id 0} {$id < [expr $opt(nn)-1]} {incr id} {
set app [$node_($id) set rca_app_]
set E [[$app getER] query]
set Etotal [expr $Etotal + $E]
}
set E [[$self getER] query]
set thresh [expr double([expr $E * $opt(num_clusters)]) / $Etotal]
}
puts "THRESH = $thresh" #以上部分为计算thresh的过程。
set clusterNodes_ ""
set TDMAschedule_ ""
if {[$self getRandomNumber 0 1] < $thresh} { #如果节点生成的随机数小于thresh 就 puts "$nodeID: *******************************************" #成为簇头
puts "$nodeID: Is a cluster head at time [$ns_ now]"
$self setClusterHead
set random_access [$self getRandomNumber 0 $opt(ra_adv)]
$ns_ at [expr $now_ + $random_access] "$self advertiseClusterHead" #在一个随机 #时间
} else { #调用函数dvertiseClusterHead告知其他节点这是一个簇头
puts "$nodeID: *******************************************"
$self unsetClusterHead
}
incr round_
set next_change_time_ [expr $now_ + $opt(ch_change)]
$ns_ at [expr $next_change_time_-0.00000001] "$node_($nodeID) delete-mark A" #为 #了nam的使用自己加的代码
$ns_ at $next_change_time_ "$self decideClusterHead" #在一个设定的时间
#opt(ch_change)后再次执行选簇函数
$ns_ at [expr $now_ + $opt(ra_adv_total)] "$self findBestCluster"
}
当一个节点被选为簇头的时候，它会调用函数advertiseClusterHead通知所以的节点，它是簇头，并且发送一个ADV类型的包。这个函数的定义也在ns-leach.tcl中，但是包的产生在传送是在内部的C++代码执行的。这里没有分析！
2、
当簇头发出了一个ADV类型的包时，其他的节点会接收这个包，并会将发送这个包的簇头的节点号按顺序先后记录在clusterChoices_中，还会计算每个簇头到接收节点的距离并记录在clusterDist_中。这样可以方便每个节点选簇的时候进行比较。具体的实现在在
ns-leach.tcl中的recvADV_CH函数中。
3、分析普通节点如何选簇
Application/LEACH instproc findBestCluster {} {
global ns_ opt node_
$self instvar now_ dist_ myADVnum_
$self instvar clusterChoices_ clusterDist_ currentCH_
set nodeID [$self nodeID]
set min_dist 100000
if [$self isClusterHead?] {
# If node is CH, determine code and create a TDMA schedule.
set dist_ $opt(max_dist)
set currentCH_ $nodeID
set myADVnum_ [[$self mac] set myADVnum_]
# There are opt(spreading) - 1 codes available b/c need 1 code
# for communication with the base station.
set numCodesAvail [expr 2 * $opt(spreading) - 1]
set ClusterCode [expr int(fmod($myADVnum_, $numCodesAvail)) + 1]
$ns_ at [expr $now_ + $opt(ra_adv_total) + $opt(ra_join)] \
"$self createSchedule" #在一个预测的时间后生成簇头的TDMA调度（同调用
} else { #函数createSchedule）
# If node is not a CH, find the CH which allows minimum transmit
# power for communication. Set the code and "distance" parameters
# accordingly.
if {$clusterChoices_ == ""} {
puts "$nodeID: Warning!!! No Cluster Head ADVs were heard!"
set currentCH_ $opt(nn) #如果一个节点没有接到簇头给它发的ADV包，那么它
$self SendMyDataToBS #将一直把数据发送给最终sink节点。
return
}
foreach element $clusterChoices_ { #普通节点选簇的过程，它是根据在
set chID [lindex $element 0] #clusterChoices_中各个簇头和它的距离
set clustID [lindex $element 2] #将距离最近的作为他的簇头。
set ind [lsearch $clusterChoices_ $element]
set d [lindex $clusterDist_ $ind]
if {$d < $min_dist} {
set min_dist $d
set currentCH_ $chID
set numCodesAvail [expr 2 * $opt(spreading) - 1]
set ClusterCode [expr int(fmod($ind, $numCodesAvail)) + 1]
}
}
set dist_ $min_dist
set random_access [$self getRandomNumber 0 \
[expr $opt(ra_join) - $opt(ra_delay)]]
$ns_ at [expr $now_ + $opt(ra_adv_total) + $random_access] \
"$self informClusterHead" #当某个节点被选为了它的簇，就掉用函数
$self GoToSleep #informClusterHead通知簇头
}
$self setCode $ClusterCode
puts "$nodeID: Current cluster-head is $currentCH_, code is $ClusterCode, \ dist is $dist_"
set clusterChoices_ ""
set clusterDist_ ""
}
从上面的分析我们知道，当一个节点选好了一个簇头，它会调用函数informClusterHead通过发送JOIN_REQ类型的包将自己的nodeID告诉触头。然后簇头会调用函数recvJOIN_REQ接收包，并将节点号nodeID记录在它的clusterNodes_中。
4、生成TDMA调度
普通节点选完簇头后，簇头会在它预设的时间调用函数createSchedule生成TDMA调度。这个函数的执行内容是：将簇头记录加入簇的所有普通节点号（clusterNodes_，这里节点号的排序是按加入簇头的顺序排的。）通过发送ADV_SCH类型的包让它簇内的节点知道。而簇内节点通过函数recvADV_SCH接收簇头发送的ADV_SCH类型的包。在函数recvADV_SCH中，节点的处理是：根据自己节点号在接收到的ADV_SCH包中的clusterNodes_数据的位置那设定自己的时隙。主要实现代码是:
set frame_time_ [expr [expr 5 + [llength [join $order]]] * $opt(ss_slot_time)]
set xmitTime_ [expr $opt(ss_slot_time) * $ind]
set end_frm_time_ [expr $frame_time_ - $xmitTime_]
set xmitat [expr [$ns_ now] + $xmitTime_]
pp "$nodeID scheduled to transmit at $xmitat. It is now [$ns_ now]."
if {[expr $xmitat + $end_frm_time_] < \
[expr $next_change_time_ - 10 * $opt(ss_slot_time)]} { $ns_ at $xmitat "$self sendData"
}
从这些代码中可以看出每个节点的发送数据的时间都是预设的。这样发送数据就不会冲突。
第一章算法概述 1.算法：解决问题的一种方法或过程；由若干条指令组成的有穷指令。 2.算法的性质： 1)输入：有零个或多个输入 2)输出：有至少一个输出 3)确定性：每条指令是清晰的、无歧义的 4)有限性：每条指令的执行次数和时间都是有限的 3.算法与程序的区别 程序是算法用某种程序设计语言的具体实现 程序可以不满足算法的有限性 4.算法复杂性分析 1)算法的复杂性是算法运行所需要的计算机资源的量，需要时间资源的量称为时间复 杂性，需要空间资源的量称为空间复杂性 2)三种时间复杂性：最坏情况、最好情况、平均情况 3)可操作性最好且最有实际价值的是最坏情况下的时间复杂性 第二章递归与分支策略 1.递归概念：直接或间接调用自身的算法 2.递归函数：用函数自身给出定义的函数 3.递归要素：边界条件、递归方程 4.递归的应用 ?汉诺塔问题 void Hanuo(int n,int a,int b,int c) { if(n==1) return; Hanuo(n-1,a,c,b); move(a,b) Hanuo(n-1,c,b,a); } ?全排列问题 void Perm(Type list[],int k,int m) { //产生list[k,m]的所有排列 if(k == m) { for(int i = 0;I <= m;i++) cout< 专业： 班级： 学号： 姓名： 日期： 2014年 11月 10日 48476Λn n 111+++=。 2、q(n ，m)=q(n ，n)，m>=n 。 最大加数n1实际上不能大于n ，因此，q(1，m)=1。 3、q(n ，n)=1+q(n ，n-1)。 正整数n 的划分由n1=n 的划分和n1<=n-1的划分组成。 4、q(n ，m)= q(n ，m-1)+q(n-m ，m)，n>m>1。 正整数n 的最大加数n1不大于m 的划分由n1=m 的划分和n1<=m-1的划分组成。 （2）、算法描述 public class 张萌 { /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub System.out .println(q (2,2)); } public static int q(int n,int m) { if ((n<1)||(m<1)) return 0; if ((n==1)||(m==1)) return 1; if (n 算法分析与设计习题集整理 第一章算法引论 一、填空题： 1、算法运行所需要的计算机资源的量，称为算法复杂性，主要包括时间复杂度和空间复杂度。 2、多项式10()m m A n a n a n a =+++L 的上界为O(n m )。 3、算法的基本特征：输入、输出、确定性、有限性 、可行性 。 4、如何从两个方面评价一个算法的优劣：时间复杂度、空间复杂度。 5、计算下面算法的时间复杂度记为： O(n 3) 。 for(i=1;i<=n;i++) for(j=1;j<=n;j++) {c[i][j]=0; for(k=1;k<=n;k++) c[i][j]= c[i][j]+a[i][k]*b[k][j]; } 6、描述算法常用的方法：自然语言、伪代码、程序设计语言、流程图、盒图、PAD 图。 7、算法设计的基本要求：正确性 和 可读性。 8、计算下面算法的时间复杂度记为： O(n 2) 。 for （i ＝1；i 《算法分析与设计》实验指导. 实验一锦标赛问题 [实验目的] 1.基本掌握分治算法的原理. 2.能用程序设计语言求解锦标赛等问题的算法; [预习要求] 1.认真阅读数据结构教材和算法设计教材,了解分治算法原理; 2.设计用分治算法求解背包问题的数据结构与程序代码. [实验题] 【问题描述】设有n=2k个运动员要进行网球循环赛。现要设计一个满足以下要求的比赛日程表： （1）每个选手必须与其他n-1个选手各赛一次； （2）每个选手一天只能参赛一次； （3）循环赛在n-1天内结束。 请按此要求将比赛日程表设计成有n行和n-1列的一个表。在表中的第i行，第j列处填入第i个选手在第j天所遇到的选手。其中1≤i≤n，1≤j≤n-1。 [实验提示] 我们可以按分治策略将所有的选手分为两半，则n个选手的比赛日程表可以通过n/2个选手的比赛日程表来决定。递归地用这种一分为二的策略对选手进行划分，直到只剩下两个选手时，比赛日程表的制定就变得很简单。这时只要让这两个选手进行比赛就可以了。 1 2 3 4 5 6 7 1 （1）（2）（3） 图1 2个、4个和8个选手的比赛日程表 图1所列出的正方形表（3）是8个选手的比赛日程表。其中左上角与左下角的两小块分别为选手1至选手4和选手5至选手8前3天的比赛日程。据此，将左上角小块中的所有数字按其相对位置抄到右下角，又将左下角小块中的所有数字按其相对位置抄到右上角，这 样我们就分别安排好了选手1至选手4和选手5至选手8在后4天的比赛日程。依此思想容易将这个比赛日程表推广到具有任意多个选手的情形。 [实验步骤] 1.设计并实现算法并准备测试用例,修改并调试程序,直至正确为止; 2.应用设计的算法和程序求锦标赛问题; 3.去掉测试程序,将你的程序整理成功能模块存盘备用. [实验报告要求] 1.阐述实验目的和实验内容; 2.阐述分治算法原理; 3.提交实验程序的功能模块; 4.记录最终测试数据和测试结果。 [思考与练习] 【金块问题】老板有一袋金块(共n块，n是2的幂（n>=2）），将有两名最优秀的雇员每人得到其中的一块，排名第一的得到最重的那块，排名第二的雇员得到袋子中最轻的金块。假设有一台比较重量的仪器，请用最少的比较次数找出最重和最轻的金块。 《计算机算法设计与分析》习题及答案 一．选择题 1、二分搜索算法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（ A ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4. 回溯法解旅行售货员问题时的解空间树是（ A ）。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树 5．下列算法中通常以自底向上的方式求解最优解的是（B ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 6、衡量一个算法好坏的标准是（ C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 7、以下不可以使用分治法求解的是（ D ）。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 8. 实现循环赛日程表利用的算法是（A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 9．下面不是分支界限法搜索方式的是（D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先 10．下列算法中通常以深度优先方式系统搜索问题解的是（D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 11.备忘录方法是那种算法的变形。（ B ） A、分治法 B、动态规划法 C、贪心法 D、回溯法 12．哈夫曼编码的贪心算法所需的计算时间为（B ）。 A、O（n2n） B、O（nlogn） C、O（2n） D、O（n） 13．分支限界法解最大团问题时，活结点表的组织形式是（B ）。 A、最小堆 B、最大堆 C、栈 D、数组 14．最长公共子序列算法利用的算法是（B）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 15．实现棋盘覆盖算法利用的算法是（A ）。 A、分治法 B、动态规划法 C、贪心法 D、回溯法 16.下面是贪心算法的基本要素的是（C ）。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、定义最优解 17.回溯法的效率不依赖于下列哪些因素（ D ） A.满足显约束的值的个数 B. 计算约束函数的时间 C.计算限界函数的时间 D. 确定解空间的时间 18.下面哪种函数是回溯法中为避免无效搜索采取的策略（B ） A．递归函数 B.剪枝函数 C。随机数函数 D.搜索函数 19. （D）是贪心算法与动态规划算法的共同点。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、最优子结构性质 20. 矩阵连乘问题的算法可由（ B ）设计实现。 A、分支界限算法 B、动态规划算法 C、贪心算法 D、回溯算法 21. 分支限界法解旅行售货员问题时，活结点表的组织形式是（ A ）。 第一部分数据结构概论及算法分析 一、选择题 1．数据结构是一门研究计算机中__ __对象及其关系的学科。 （1）数值运算（2）非数值运算（3）集合（4）非集合 2．数据结构的定义为(K，R)，其中K是__ __的集合。 （1）算法（2）数据元素（3）数据操作（4）逻辑结构 3．算法分析的目的是____。 （1）找出数据结构的合理性（2）研究算法中输入和输出的关系 （3）分析算法的效率以求改进（4）分析算法的易懂性和文档性 4. 数据的不可分割的基本单位是_ ___。 A.元素 B.结点 C.数据类型 D.数据项 5．下列算法suanfa2的时间复杂度为____。 int suanfa2(int n) { int t=1； while(t<=n) t=t*2； return t； } A.O(log2n) B.O(2n) C.O(n2) D.O(n) 6.（）是具有相同特性数据元素的集合，是数据的子集。 A 数据符号 B 数据对象 C 数据 D 数据结构 7．与数据元素本身的形式、内容、相对位置、个数无关的是数据的( )。 A. 存储结构 B. 逻辑结构 C. 算法 D. 操作 8．数据结构是研究数据的（）及它们之间的相互联系。 A、理想结构，物理结构b、理想结构，逻辑结构 C、物理结构，逻辑结构d、抽象结构，逻辑结构 9．组成数据的基本单位是（）。 a、数据项 b、数据类型 c、数据元素 d、数据变量 10．数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为： （A）存储结构（B）逻辑结构（C）顺序存储结构（D）链式存储结构11．算法指的是（） A．计算机程序B．解决问题的计算方法 C．排序算法D．解决问题的有限运算序列 12．下列算法suanfa1中语句"x=x*2；"的执行次数是（）。 void suanfa1(int n) { int i,j,x=1； for(i=1；i<=n；i++) for(j=i；j<=n；j++) x=x*2； printf("%d",x)； } A.n(n-1)/2 B.n(n+1)/2 C.n2 D.?nlog2n? 13. 由____组成的集合是一个数据对象。 A.不同类型的数据项 B.不同类型的数据元素 C.相同类型的数据项 D.相同类型的数据元素 14．在下列选项中，哪个不是一个算法一般应该具有的基本特征_____。 A. 确定性 B. 可行性 C. 无穷性 D. 拥有足够的情报15．在计算机中，算法是指______。 A. 查询方法 B. 加工方法 C. 解题方案准确而完整的描述 D. 排序方法16．算法的时间复杂度是指________。 A. 执行算法程序所需要的时间 B. 算法程序的长度 C. 算法执行过程中所需要的基本运算次数 D. 算法程序中的指令条数17．算法的空间复杂度是指________。 A. 算法程序的长度 B. 算法程序中的指令条数 C. 算法程序所占的存储空间 D. 算法执行过程中所需要的存储空间18．下面叙述正确的是_______。 A. 算法的执行效率与数据的存储结构无关 B. 算法的空间复杂度是指算法程序中指令（或语句）的条数 C. 算法的有穷性是指算法必须能在执行有限个步骤之后终止 D. 以上三种描述都不对 19．数据的存储结构是指______。 维吉尼亚算法分析及应用 一．实验目的 通过应用维吉尼亚算法对数据进行加解密的操作，了解维吉尼亚的加解密的机制，加深对维吉尼亚的算法理解 二．试验环境 安装Windows操作系统的PC机，具有C语言编译环境 三．试验原理 加密过程很简单，就是给定密码字母X和明文字母Y，密文字母是位于X行和Y列的那个字母。这样就决定了加密一天消息与消息一样长的密钥字符串，通常，迷药字符串事是密钥的重复。 使用查表的方式多加密几次就能很轻易的总结出规律：将A-Z以0-25编号，那么加密过程就是，在代换表的第一行中找到消息字母，如W，然后向后移D次（即3次），所得的字母就是密文了。如果数到末位，那么下一次移位就是从头（即A）继续也就是说，可以将A-Z看成一个环，加密过程就是找到消息字母后，将指针往环的某个特定方向移位，次数就是密钥字母所代表的数字，这其实是一个模26的过程。 扩展一下，以上加密仅能对26个字母进行加密，而且不能区分大小写，但其实英文中除了字母外，还有标点符号，还有空格。如果考虑到大部分英文字符，那个维吉尼亚代换表将比较大，而且有点浪费空间，如果能将被加密的字符有N个如果把这N个字符建成一个环，那么加密过程即使模N的过程，即C(I)=K(I)+P(I)modN，其中，K，C，P分别代表的是密钥空间，密文空间，消息（明文）空间。 四．主要代码 #include 无线传感器网络LEACH算法的综合改进 陈楠，徐塞虹 北京邮电大学计算机科学与技术学院，北京（100876） E-mail：chennan6062@https://www.doczj.com/doc/204000801.html, 摘要：本文通过研究无线传感器网络的层次型路由协议LEACH算法，指出了其存在的一些缺点，并对其某些改进算法进行深入研究，在此基础上进一步改进，吸取已有算法的优点，弥补其中的不足，提出了一种新的分簇算法及簇的维护算法。 关键词：无线传感器网络，层次型路由协议，LEACH算法，改进 中图分类号：TP393 1.引言 传感器技术、通信技术和计算机技术是现代信息技术的三大支柱，它们分别完成对被 测量对象的信息提取、信息传输及信息处理。将这三种技术融合在一起的无线传感器网络技术给人们生活的各个领域带来了极大的影响。作为一种全新的技术，无线传感器网络给科技工作者提出了很多具有挑战性的课题，其中路由协议就是热点之一，传统网络的路由协议远远不能满足无线传感器网络的特点和要求，因此，该领域具有很大的研究价值[1]。本论文在已经提出来的分层次路由协议的基础上进行进一步改进，从而使网络性能又进一步的提升。 2.研究背景 无线传感器网络是由大量功率低、体积小、价格便宜的传感器节点组成的，这些节点实时监测、感知和采集网络分布区域内的各种环境或者被监测对象等诸多用户所感兴趣的信息，并对这些信息进行分布式处理，随后传递给用户，使用户随时随地都可以获取所需的信息。由于传感器网络所具有的特点，其应用前景十分广泛。 但是由于无线传感器网络这些特点的存在，导致节点能量资源、计算能力和带宽等资源都非常有限，尤其是其有限的能量直接影响传感器网络的生命周期以及网络的信息质量。因此，设计有效的策略，降低节点能源损耗，提高网络生命周期成为无线传感器网络的核心问题。 影响节点能源损耗的因素有很多，其中最重要的就是路由协议以，但是传统的那些路由协议应用于无线传感器网络中在某些方面存在一定的缺陷，所以基于传统路由协议，W.R Heinzelman等人提出了低功耗自适应集群型分层路由协议（Low Energy Adaptive Clustering Hierarchy Protocol），LEACH协议[2]是第一个在无线传感器网络中提出的层次式路由协议，其后的大部分层次式路由协议都是在它的基础上发展而来的。该算法主要是通过随机选择簇头，平均分担中继通信业务来实现能量消耗的减少，与一般的平面多跳路由协议和静态成簇算法相比，LEACH可以将网络的生命周期延长15%。 3.LEACH算法概述 LEACH（Low energy adaptive clustering hierarchy）是一种以最小化传感器网络能量损耗为目标的分层式协议，它既可以作为一种传感器网络的基本路由协议，也可以作为传感器网络的拓扑控制算法，因为协议在形成分层式拓扑结构的同时，也确定了簇首，决定了网络的路由。 第一章 什么是算法 算法是解决一个计算问题的一系列计算步骤有序、合理的排列。对一个具体问题（有确定的输入数据）依次执行一个正确的算法中的各操作步骤，最终将得到该问题的解（正确的输出数据）。 算法的三个要素 1).数据: 运算序列中作为运算对象和结果的数据. 2).运算: 运算序列中的各种运算:赋值,算术和逻辑运算 3).控制和转移: 运算序列中的控制和转移. 算法分类 从解法上：数值型算法:算法中的基本运算为算术运算；非数值型算法:算法中的基本运算为逻辑运算. 从处理方式上：串行算法:串行计算机上执行的算法；并行算法:并行计算机上执行的算法 算法的五个重要的特性 （1） 有穷性：在有穷步之后结束。 （2） 确定性：无二义性。 （3） 可行性：可通过基本运算有限次执行来实现。 （4） 有输入 表示存在数据处理 （5） 有输出 伪代码 程序设计语言（PDL ），也称为结构化英语或者伪代码，它是一种混合语言，它采用一种语言（例如英语）的词汇同时采用类似另外一种语言（例如，结构化程序语言）的语法。 特点：1)使用一些固定关键词的语法结构表达了结构化构造、数据描述、模块的特征； 2)以自然语言的自由语法描述了处理过程；3)数据声明应该既包括简单的也包括复杂的数据结构；4)使用支持各种模式的接口描述的子程序定义或者调用技术。 求两个n 阶方阵的相加C=A+B 的算法如下，分析其时间复杂度。 #define MAX 20 ∑∑∑∑-=-=-=-=====102101010*11n i n i n i n j n n n n n n n n )O()1O(1O(11i i j i j ==∑∑==）)O(N )21O()O()O(21N 1=+=∑=∑==)(N N i i N i i 赋值，比较，算术运算，逻辑运算，读写单个变量（常量）只需1单位时间 2). 执行条件语句 if c then S1 else S2 的时间为TC +max(TS1,TS2). 3). 选择语句 case A of a1: s1；a2: s2；...； am: sm 需要的时间为 max （TS1,TS2 ,..., TSm ）. 4). 访问数组的单个分量或纪录的单个域需要一个单位时间. 5). 执行for 循环语句的时间=执行循环体时间*循环次数. 6). while c do s (repeat s until c)语句时间=(Tc+Ts)*循环次数. 7). 用goto 从循环体内跳到循环体末或循环后面的语句时,不需额外时间 8). 过程或函数调用语句：对非递归调用，根据调用层次由里向外用规则1-7进行分析； 对递归调用，可建立关于T(n)的递归方程,求解该方程得到T(n). 大学 《数据结构与算法分析》课程 习题及参考答案 模拟试卷一 一、单选题（每题 2 分，共20分） 1.以下数据结构中哪一个是线性结构？( ) A. 有向图 B. 队列 C. 线索二叉树 D. B树 2.在一个单链表HL中，若要在当前由指针p指向的结点后面插入一个由q指向的结点， 则执行如下( )语句序列。 A. p=q; p->next=q; B. p->next=q; q->next=p; C. p->next=q->next; p=q; D. q->next=p->next; p->next=q; 3.以下哪一个不是队列的基本运算？（） A. 在队列第i个元素之后插入一个元素 B. 从队头删除一个元素 C. 判断一个队列是否为空 D.读取队头元素的值 4.字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成( ) 个不同的字符串？ A.14 B.5 C.6 D.8 5.由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为( )。 以下6-8题基于图1。 6.该二叉树结点的前序遍历的序列为( )。 A.E、G、F、A、C、D、B B.E、A、G、C、F、B、D C.E、A、C、B、D、G、F D.E、G、A、C、D、F、B 7.该二叉树结点的中序遍历的序列为( )。 A. A、B、C、D、E、G、F B. E、A、G、C、F、B、D C. E、A、C、B、D、G、F E.B、D、C、A、F、G、E 8.该二叉树的按层遍历的序列为( )。 A．E、G、F、A、C、D、B B. E、A、C、B、D、G、F C. E、A、G、C、F、B、D D. E、G、A、C、D、F、B 9.下面关于图的存储的叙述中正确的是( )。 A．用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关 B．用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关 C. 用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关 D．用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关 10.设有关键码序列(q，g，m，z，a，n，p，x，h)，下面哪一个序列是从上述序列出发建 堆的结果?( ) A. a，g，h，m，n，p，q，x，z B. a，g，m，h，q，n，p，x，z C. g，m，q，a，n，p，x，h，z D. h，g，m，p，a，n，q，x，z 二、填空题（每空1分，共26分） 1.数据的物理结构被分为_________、________、__________和___________四种。 2.对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为_________， 在表尾插入元素的时间复杂度为____________。 3.向一个由HS指向的链栈中插入一个结点时p时，需要执行的操作是________________; 删除一个结点时，需要执行的操作是______________________________（假设栈不空而 且无需回收被删除结点）。 4.对于一棵具有n个结点的二叉树，一个结点的编号为i(1≤i≤n)，若它有左孩子则左 孩子结点的编号为________，若它有右孩子，则右孩子结点的编号为________，若它有 双亲，则双亲结点的编号为________。 5.当向一个大根堆插入一个具有最大值的元素时，需要逐层_________调整，直到被调整 到____________位置为止。 6.以二分查找方法从长度为10的有序表中查找一个元素时，平均查找长度为________。 7.表示图的三种常用的存储结构为_____________、____________和_______________。 8.对于线性表（70，34，55，23，65，41，20）进行散列存储时，若选用H（K）=K %7 作为散列函数，则散列地址为0的元素有________个，散列地址为6的有_______个。 9.在归并排序中，进行每趟归并的时间复杂度为______，整个排序过程的时间复杂度为 ____________，空间复杂度为___________。 10.在一棵m阶B_树上，每个非树根结点的关键字数目最少为________个，最多为________ 个，其子树数目最少为________，最多为________。 三、运算题（每题 6 分，共24分） 1.写出下列中缀表达式的后缀形式： （1）3X/(Y-2)+1 （2）2+X*(Y+3) 2.试对图2中的二叉树画出其： (1)顺序存储表示的示意图； (2)二叉链表存储表示的示意图。 3.判断以下序列是否是小根堆? 如果不是, 将它调 图2 整为小根堆。 （1）{ 12, 70, 33, 65, 24, 56, 48, 92, 86, 33 } （2）{ 05, 23, 20, 28, 40, 38, 29, 61, 35, 76, 47, 100 } 4.已知一个图的顶点集V和边集E分别为： V={1,2,3,4,5,6,7}; ---------------------------------------------------------------最新资料推荐------------------------------------------------------ 1算法分析的目的是( 1. 算法分析的目的是( ) A. 找出数据结构的合理性 B. 找出算法中输入和输出之间的关系 C. 分析算法的易懂性和 可靠性 D. 分析算法的效率以求改进【参考答案】 D 2. 在 单链表中，增加头结点的目的是( ) A. 方便运算的 B. 使单链表至少有一个结点 C. 标识表结点中首结点的位置 D. 说明单链表是线性表的链式存储实现【参考答案】 A 3. 软件 开发离不开系统环境资源的支持，其中必要的测试数据属于( ) A. 硬件资源 B. 通信资源 C. 支持软件 D. 辅助资源【参考 答案】 D 4. 分布式数据库系统不具有的特点是( ) A. 数 据分布性和逻辑整体性 B. 位置透明性和复制透明性 C. 分布性 D. 数据冗余【参考答案】 D 5. 下列数据模型中，具有坚实 理论基础的是( ) A. 层次模型 B. 网状模型 C. 关系模 型 D. 以上 3 个都是【参考答案】 C 6. 栈底到栈顶依次 存放元素 A、 B、 C、 D，在第五个元素 E 入栈前，栈中元素可 以出栈，则出栈序列可能是( ) A. ABCED B. DCBEA C. DBCEA D. CDABE 【参考答案】 B 7. 在结构化程序设计思想提 出之前，在程序设计中曾强调程序的效率，现在，与程序的效率相比，人们更重视程序的( ) A. 安全性 B. 一致性 C. 可 理解性 D. 合理性【参考答案】 C 8. 软件开发的结构化生命 周期方法将软件生命周期划分成( ) A. 定义、开发、运行 1 / 14 * https://www.doczj.com/doc/204000801.html, * * Created on: 2011-4-17 * Author: syj */ #include 算法是，对特定问题求解方法和步骤的一种描述，它是有限指令的有限序列，其中每个指令表示一个或多个操作。 算法与程序的比较 ?算法是解决问题的一种方法或一个过程，考虑如何将输入转换成输出，一个问题可以有多种算法。 ?程序是用某种程序设计语言对算法的具体实现。 ?程序 = 数据结构 + 算法 算法的特性 一个算法必须具备以下五个重要特性： ?有穷性一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。 ?确定性算法中每一条指令必须有确切的含义，没有二义性，在任何条件下只有唯一的一条执行路径，即对相同的输入只能得到相同的输出。 ?可行性算法是可执行的，算法描述的操作可以通过已经实现的基本操作执行有限次来实现。 ?输入一个算法有零个或多个输入 ?输出一个算法有一个或对个输出 算法设计有正确性（Correctness）、可读性（Readability）、健壮性（Robustness）、高效性（Efficiency）的基本要求。 一个好的算法首先要具备正确性，然后是健壮性，可读性，在几个方面都满足的情况下，主要考虑算法的效率，通过算法的效率高低来评判不同算法的优劣程度。 算法效率分析 算法效率主要从一下两个方面来考虑： 1.时间效率：指的是算法所耗费的时间； 2.空间效率：指的是算法执行过程中所耗费的存储空间。 时间效率和空间效率有时候是矛盾的。 时间效率分析 一个算法在计算机上运行所耗费的时间大致可以等于计算机执行一种简单的操作（如赋值、比较、移动等）所需的时间与算法中进行简单操作次数的乘积。 算法运行时间 = 一个简单操作所需的时间 x 简单操作次数， 也就是算法中每条语句的执行时间之和 每条语句执行一次所需的时间，一般是随机器而异的，取决于机器的指令性能、速度以及编译的代码质量，是由机器本身软硬件环境决定的，它与算法无关。所以，可以假设执行每条语句所需的时间均为单位时间。此时对算法的运行时间的讨论就可以转化为讨论改算法中所有语句的执行次数了。 例如：两个n x n矩阵相乘的算法课描述为： for(i=1;i<=n;i++) //n+1次 for(j=1;j<=n;j++) //n(n+1)次 { c[i][j]=0; //n*n次 for(k=0;k 《算法分析与设计》课程教学大纲 【课程编号】：14314025 【英文译名】：Analysis and Design of Computer Algorithms 【适用专业】：软件工程、计算机科学与技术、信息安全 【学分数】：3 【总学时】：48学时 【实践学时】：0 一、本课程教学目的和课程性质 本课程是软件工程、计算机科学与技术、信息安全等专业的选修课程，也可作为其它计算机相关专业的选修课程。课程属于专业教育课。 课程主要介绍计算机算法分析、算法设计及复杂性理论的基本概念、基本的算法分析方法和常用的算法设计方法。通过本课程的教学，强化学生算法分析与设计的基础理论知识，使学生掌握计算机算法分析的基本方法及常见的算法设计方法（如：分治法、回溯法、贪心法、动态规划法、分枝限界法等）。通过学习，学生能够用利用常见的算法设计方法来解决软件开发中的实际问题。培养扎实的专业知识和基本技能和从事应用软件开发和测试的能力。 二、本课程的基本要求 本课程的基本要求是让学生理解计算机算法效率分析与设计所涉及的基本概念和基础知识，掌握基本的算法分析方法和常见的算法设计方法，能熟练应用课程介绍的算法设计方法来解决软件开发中的实际问题。通过对算法实例的分析，进一步加深学生对算法设计方法的认识和理解。 1、理解算法的基本概念和算法的效率分析方法。 2、理解分治策略的原理、效率分析，掌握分支策略在常见问题（如：二分检索、归并分类、快速排序、选择问题等）问题中的应用。了解分治策略的变形（减治策略、变治策略）的思想和简单应用。 3、理解动态规划的原理、适用条件，了解算法的效率，掌握该算法在常见问题（如：多段图、最优二分检索树、0/1背包问题、货郎担问题、可靠性设计等）问题中的应用。 4、理解贪心方法的原理、效率分析方法，掌握在常见问题（如：背包问题、带有期限的作业排序、最小生成树、单源点最短路径等）问题中的应用。 5、理解回溯法的原理，掌握在常见问题（如：8-皇后、子集和数、图的着色、哈密顿环等）问题中的简单应用。 6、了解分支-限界方法的基本思想和简单应用。 7、了解基本的检索和周游方法的基本思想。 8、了解NP-难度和NP-完全问题基本思想和简单应用。 9、了解概率算法的基本思想及简单应用。 三、本课程与其他课程的关系 XXXX大学 算法设计与分析课程设计报告 院（系）： 年级： 姓名： 专业：计算机科学与技术 研究方向：互联网与网络技术 指导教师： XXXX 大学 目录 题目1 电梯调度 (1) 1.1 题目描述 (1) 1.2 算法文字描述 (1) 1.3 算法程序流程 (4) 1.4 算法的程序实现代码 (10) 题目2 切割木材 (12) 2.1题目描述 (12) 2.2算法文字描述 (12) 2.3算法程序流程 (13) 2.4算法的程序实现代码 (18) 题目3 设计题 (20) 3.1题目描述 (20) 3.2 输入要求 (20) 3.3输出要求 (20) 3.4样例输入 (20) 3.5样例输出 (20) 3.6测试样例输入 (21) 3.7测试样例输出 (21) 3.8算法实现的文字描述 (21) 3.9算法程序流程 (22) 3.10算法的程序实现代码 (23) 算法分析与设计课程总结 (26) 参考文献 (27) 题目1电梯调度 1.1 题目描述 一栋高达31层的写字楼只有一部电梯，其中电梯每走一层需花费4秒，并且在每一层楼停靠的时间为10秒，乘客上下一楼需要20秒，在此求解最后一位乘客到达目的楼层的最短时间以及具体的停靠计划。例如：此刻电梯停靠需求为4 5 10（有三位乘客，他们分别想去4楼、5楼和10楼），如果在每一层楼都停靠则三位乘客到达办公室所需要的时间为3*4=12秒、4*4+10=26秒、4*9+2*10=56秒，则最后一位乘客到达办公室的时间为56秒，相应的停靠计划为4 5 10均停靠。对于此测试用例电梯停靠计划方案：4 10，这样到第4楼的乘客所需时间为3*4=12秒，到第5楼的乘客所需时间为3*4+20=32秒，到第10楼的乘客所需时间为9*4+10=46秒，即最后到达目的楼层的顾客所需时间为46秒。 输入要求： 输入的第1行为整数n f1 f2 … fn，其中n表示有n层楼需要停靠，n=0表示没有更多的测试用例，程序终止运行。f1 f2 … fn表示需要停靠的楼层（n<=30，2<=f1 －、选择题 1.算法分析的目的是( ) A.找出数据结构的合理性 B.找出算法中输入和输出之间的关系 C. 分析算法的易懂性和可靠性 D. 分析算法的效率以求改进 【参考答案】D 2.在单链表中，增加头结点的目的是( ) A.方便运算的 B.使单链表至少有一个结点 C.标识表结点中首结点的位置 D.说明单链表是线性表的链式存储实现 【参考答案】A 3.软件开发离不开系统环境资源的支持，其中必要的测试数据属于( ) A.硬件资源 B.通信资源 C.支持软件 D.辅助资源 【参考答案】D 4.分布式数据库系统不具有的特点是( ) A.数据分布性和逻辑整体性 B.位置透明性和复制透明性 C.分布性 D.数据冗余 【参考答案】D 5.下列数据模型中，具有坚实理论基础的是( ) A.层次模型 B.网状模型 C.关系模型 D.以上3个都是 【参考答案】C 6.栈底到栈顶依次存放元素A、B、C、D，在第五个元素E入栈前，栈中元素可以出栈，则出栈序列可能是( ) A.ABCED B.DCBEA C.DBCEA D.CDABE 【参考答案】B 7.在结构化程序设计思想提出之前，在程序设计中曾强调程序的效率，现在，与程序的效率相比，人们更重视程序的( ) A.安全性 B.一致性 C.可理解性 D.合理性 【参考答案】C 8.软件开发的结构化生命周期方法将软件生命周期划分成( ) A.定义、开发、运行维护 B.设计阶段、编程阶段、测试阶段 C.总体设计、详细设计、编程调试 D.需求分析、功能定义、系统设计 【参考答案】A 9.在数据管理技术发展过程中，文件系统与数据库系统的主要区别是数据库系统具有( ) A.特定的数据模型 B.数据无冗余 C.数据可共享 D.专门的数据管理软件 【参考答案】A 10.实体是信息世界中广泛使用的一个术语，它用于表示( ) A.有生命的事物 B.无生命的事物 C.实际存在的事物 D.一切事物 【参考答案】C 11.下面叙述中正确的是（） A.C语言编译时不检查语法 LEACH协议的改进算法 夏北浩 （湖南大学信息科学与工程学院长沙410082） 摘要：首先介绍了LEACH协议的工作原理，性能分析以及不足。之后介绍了LEACH的改进算法。 关键词：无线传感器网络,LEACH协议,改进算法,能量消耗 Improved algorithm of LEACH Xia Beihao (The College of Information Science and Engineering, Hunan University 410082) Abstract: This paper firstly introduce the content of the working principle of LEACH , the analysis of performance and discourages,following the introduction of the improved algorithm LEACH . Key: wireless sensor networks, LEACH protocol,Improved Algorithm,Energy consumption 1 引言 近年来，由于无线技术、计算机技术与传感器技术的迅猛发展和快速融合，无线传感器网络应运而生。无线传感器网络技术作为一种新型网络技术受到研究者的普遍重视和广泛研究。但传感器网络也有一些固定的缺点：能量利用率低、生存周期短、抗干扰能力差。通过良好的算法不仅可以减少传感器节点的能耗，还可以降低通信干扰，提高mac协议和路由协议的效率。因此，提出一个高效稳定合理的算法便成为迫切需要解决的问题。 2 LEACH协议的介绍 2.1 LEACH协议 LEACH是WSN中第一个基于分簇的路由算法，它将网络中的节点分为簇头节点和簇内节点。由于簇头节点需要协调簇内节点的工作，负责数据的融合和转发，能量消耗相对较大，所以LEACH采用周期性地随机选择簇头节点以均衡网络中节点能量消耗。从而达到延长网络生命周期目的。LEACH协议以“轮”作为运算法分析与设计
算法分析与设计习题集整理
《算法设计与分析》实验指导
《计算机算法设计与分析》习题及答案
第一部分数据结构概论及算法分析答案
维吉尼亚算法分析及应用
无线传感器网络LEACH算法的综合改进
算法分析与设计
数据结构与算法分析习题与参考答案
1算法分析的目的是(
LEACH算法源代码
算法与算法分析
《算法设计与分析》教学大纲
算法分析与设计-课程设计报告
1算法分析的目的是(
LEACH算法的改进
相关主题
文本预览