无线自组传感器网络中基于能量的超宽带多路径路由算法英文

6LowPAN--低速无线个域网标准3G--第三代移动通信技术ASR--自动语音识别A TIS--铁路车号自动识别系统ANN--人工神经元网络AGPS--网络辅助GPSAPIS--非距离定位算法AOA--基于信号到达角度的方法Bluetooth--蓝牙技术CDMA--码分多址CSMA/CA--载波真听多路访问方式DNS--域名解析服务DSSS--直接序列展频（扩频）技术DAS--直接存储DP--动态程序对比法DTW--动态时间归正技术ETC--电子不停车收费EPCIS--EPC信息服务EPC--电子产品编码EPC--头字段--EPC HeaderEPC--Manager--管理者FFD--全功能设备FHSS--跳频展频（扩频）技术GS1--全球统一标识系统GFS--Google文件系统GPS--全球定位系统GTIN--全球贸易识别代码HART--可寻址远程传感器高速通道的开放通信协议HMM--隐马尔可夫模型IOT--实物物联网IaaS--基础设施服务、云设备IEEE--美国电气和电子工程师协会ISO--国际标准化组织IEC--国际电工委员会IPv6--Internet Protocol V ersion 6互联网协议IETF--互联网工程任务组IrDA--红外数据组织LP--线性预测LBS--位置服务LTS--轻量基于树形分布的同步算法Location Tags--识别标识MTSO--移动电话交换局M2M--“机器对机器”Modem--调制解调器Microcell--微蜂窝系统MEMS--微机电系统MAC--媒体访问控制协议MA_HN--无线自组网NM--窄带微波NTP--网络时间协议NAS--网络附加存储NFC--近距离无线通信OCR--光学字符识别ONS--对象名称解析服务O FDM--正交频分复用ONS--对象名称解析服务PML--实体标记语言PML--物理(实体）标示语言PA--能量感知路由协议PHY--网络的物理层POS--个人操作空间PaaS--平台即服务、云平台PML--物理标示语言PAN--个人区域网络PG1--国际标准化PG2--标准体系与构架系统PG3--通信与信息交互PG4--协同信息处理PG5--标识PG6--安全PG7--接口PG8--电力行业应用调研PLP--感知线性预测PLC--可编程逻辑控制器QDMA--正交分割多址介入RSSI--基于接收信号强度的方法RBS--参考广播时钟同步协议RTS/CTS--协议--请求发送/允许发送协议RFID--射频识别RFD--精简功能设备SIM--用户识别卡Serial Number--序列号SaaS--软件即服务、云软件SOA--面向服务的体系架构SAN--存储区域网络Savant--神经网络软件、中间件SE--敏感元件SN--传感器节点Sink N--汇聚节点TMS--任务管理系统TE--转换原件TC--变换电路TOA--基于信号传输时间的方法TDOA--基于信号传输时间差的方法TPSN--用于传感器网络的时间同步协议UWB--超宽带技术（无线载波通信技术）UTC--世界标准时间UID--泛在识别{用户身份证明}WSN--无线传感器网络WMAN--无线城域网WPAN--无线个域网WSN--无线传感网络WPAN--无线个人区域网络WCDMA--宽带码分多址XML--可扩展标记语言。

2009 15th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications Multi-Path Planning for Mobile Element to Prolong the Lifetime ofWireless Sensor Networks∗Dakai Zhu,Yifeng Guo and Ali S¸aman TosunUniversity of Texas at San AntonioSan Antonio,TX78249{dzhu,yguo,tosun}@AbstractMobile elements,which can traverse the deploymentarea and convey the observed data from static sensor nodesto a base station,have been introduced for energy efficientdata collection in wireless sensor networks(WSNs).How-ever,most existing solutions only plan a single path for themobile element,which may lead to quick energy depletionfor the sensor nodes that are far away from the path.In thispaper,for data collection in WSNs,we study the multi-pathplanning(MPP)problem for the mobile element to prolongthe lifetime of WSNs.Observing the intractability of theproblem,two MPP heuristic schemes,namelyfixed-K andadaptive-K,are proposed.The central idea of these schemesis to plan multiple paths and have the mobile element followthem in turn to balance the energy consumption on individ-ual sensor nodes,thus extending the lifetime of WSNs.Theproposed schemes are evaluated through extensive simula-tions.The results show that,compared to that of the singlepath solution,the multi-path approaches can extend the life-time of WSNs by up to four times.Moreover,the adaptive-Kscheme treats the sensor nodes more fairly with less varia-tion on their energy consumptions.1IntroductionIn the recent past,the popularity of wireless sensor net-works(WSNs)has been manifested by their deploymentin many real-life applications(e.g.,habitat study[13]andecology monitoring[19]).With potentially a large numberof sensor nodes scattered in a region of interest,one of thechallenging problems in WSNs is how to efficiently aggre-gate the data sampled at each node to a base station,whichhas the computational power to store and process all thecollected data[1,7].Note that,sensor nodes are generallylead to uneven energy depletion rates for the sensor nodes in WSNs,especially for the cases where the mobile ele-ment needs to collect data directly from every sensor node but it cannot visit the location of all sensor nodes(due to, for example,energy budget of the mobile element or time limitations).The sensor nodes that are far away from the path will need to transmit their data to the mobile element at higher power levels and thus use up their energy budget more quickly.For WSNs that rely on all their sensor nodes for normal operations,such uneven energy depletion will lead to limited lifetime of WSNs.Different from the existing single-path solutions,in our preliminary study,we have proposed the idea of exploit-ing multiple paths for the mobile element in WSNs to ex-tend the WSN’s lifetime[25].However,no detailed algo-rithm and simulation results were reported in the prelimi-nary work.In this paper,for the problem of data collection in WSNs using a single mobile element that collects data directly from every sensor node,we study systematically the multi-path planning(MPP)problem.The key idea is to calcu-late multiple paths for the mobile element,which will be followed in turn during data collection in order to balance the energy consumption on individual sensor nodes,thus to extend the lifetime of the WSNs.After showing the intractability of the problem,we study two MPP heuristic schemes,fixed-K and adaptive-K,based on different path planning strategies.The proposed heuristic schemes are evaluated through extensive simulations.The results show the superiority of the proposed multi-path schemes on ex-tending the lifetime of WSNs when compared to that of single-path solutions(e.g.,up to4times with20paths).The remainder of the paper is organized as follows.Sec-tion2presents the system models and states our assump-tions.Section3illustrates the problem with a motivational example and formalizes the problem.The multi-path plan-ning heuristics are presented in Section4and simulation results are discussed in Section5.Section6discusses the related work.Section7concludes the paper and points out the directions for our future work.2System Models and AssumptionsThe WSN considered in this work consists of a setΦof n sensor nodes,a base station(BS)and a mobile element.The n sensor nodes are statically deployed in thefield of interest where node N i(i=1,...,n)is at location(x i,y i),whichis assumed to be known a priori.So does the location of the base station at(x0,y0).Departing from the base station, the mobile element needs to travel through thefield,collect data directly from all the sensor nodes and return to the base station for conveying the collected data(and/or recharging) within a given time interval T.Here,the time interval T could be determined by the data sampling rate and buffer size on the sensor nodes[10],or by the amount of available energy(after being fully recharged)to drive the mobile el-ement.We further assume that the mobile element moves at a constant speed S and the maximum length of its travel path(PH)should be no more than L=S·T.Suppose that the distance from a sensor node to the travel path of the mobile element is d(which is defined as the minimum distance from the location of the sensor node to the nearest point on the travel path).During data collec-tion,when the sensor node transmits its data to the mobile element through wireless communication,it is well-known that the required transmission power directly depends on the distance d,which can be modeled as[15]:P(d)=γ+αdβ(1) whereγandαare system dependent parameters and2≤β≤4.And,in general,γis a small constant.Modern sensor nodes normally have a few discrete power levels that can transmit data in different ranges(e.g., Tmote Sky sensors have32different power levels[16]).In this paper,we assume that the sensor nodes considered have m different power levels,which are represented as m cou-ples:(P1,R1),...,(P m,R m),where R i is the transmission range when sensor nodes transmit at power level P i.Here, the maximum transmission power level P max=P m lim-its the maximum transmission range to be d max=R m. For instance,Tmote Sky sensor nodes can transmit up to 125meters at its maximum transmission power level[16]. Note that,the maximum distance from any sensor node to the travel paths of the mobile element should be no more than d max(otherwise,the mobile element will not be able to directly collect the data from such sensor node).More-over,the minimum transmission power level P min=P1 allows the sensor nodes to transmit data up to distance of d min=R1(e.g.,when Tmote Sky sensor nodes transmit at the lowest power level,the smallest range is measured to be around0.15meter).Assuming that the sensor nodes have the same constant sampling rate,the amount of data collected at each node will be the same during any time interval T.Suppose that the wireless data transmission speed does not depend on the transmission power(which only affects the transmis-sion range),the data transmission time t will be a constant value.Suppose that d i is the distance from the location of sensor node N i to a travel path P H.When the mobile el-ement follows the path P H during one round of data col-lection,the amount of energy consumed by the sensor node N i for transmitting its data to the mobile element will be E i=P x·t,where the power level P x corresponds to R x with R x−1<d i≤R x.That is,the energy consumption of a sensor node to transmit its data depends solely on d i.Therefore,if the mobile element could visit the location26(a)4×4field with 8sensors 26(b)Singlepath 26(c)Twopaths 26(d)Four pathsFigure 1.Motivational example:path planning for the mobile element.of each and every sensor node (that is,the distance from ev-ery sensor node to the travel path of the mobile element is no more than d min ),all sensor nodes can transmit their data to the mobile element at their minimum power level P min with minimized energy consumption,which in turn maxi-mizes the WSN’s lifetime.In this paper,we consider the cases where the path length L of the mobile element is not enough for it to visit all the sensor nodes.Therefore,for the sensor nodes that are not on the mobile element travel path during one round of data collection,they need to transmit at a power level higher than P min for the mobile element to successfully receive their data.Moreover,we assume that the WSN is functional only if all sensor nodes are alive (i.e.,when any sensor node uses up its energy and dies,the WSN will die).In other words,assuming that all sensor nodes have the same energy budget at their initial deployment,the lifetime of the WSN depends on the sensor node that con-sumes the highest amount of energy.In what follows,before formally presenting the problem,we illustrate the problem through a concrete example.3Motivational ExampleWe consider an example with 8sensor nodes placed on a 4×4grid field as shown in Figure 1(a).Here,the base sta-tion is located at (0,0).For illustration purpose,we assume that the mobile element needs to follow the grid on the field.Suppose that the grid size is 1and the path length limit of the mobile element is 10.It can be easily seen that it is not possible for the mobile element to visit each and every sen-sor node during one round of data collection within its path length limit.Assume that the power consumption for the sensor nodes is modeled as in Equation 1and γ=0,α=1,β=2,Pmax =2(i.e.,d max=√2),P 0.1)aP P 111119N 116N 113N 113N 9N 9N19After each path is followed3times,the corresponding en-ergy consumption for the nodes during12rounds of data collection is shown in the fourth column(labeled as path set P S3)of Table1.Here,the maximum energy consump-tion for the nodes is only9.6units(for nodes N2and N7). Compared to that of the case with two paths,the four-path option can achieve about25%more lifetime for the WSN.3.1Problem FormulationAssuming that the WSN under consideration can operate until thefirst node uses up its energy and dies,for a given path number K,the objective of this work is tofind an ef-ficient approach to construct the appropriate set of K paths for the mobile element,such that the energy consumption for the most energy-hungry sensor node is minimized.Define E i,j as the energy consumption for the sensor node N i when the path P H j is followed by the mobile ele-ment,we have:E i,j=P(d j i)·t(2) where d j i is the shortest distance from the path P H j to the location of sensor node N i and P(d j i)is the corresponding power level.Moreover,when the constructed K paths are followed in turn by the mobile element,the average energy consumption for sensor node N i during one round of data collection is defined as:E i= Kj=1E i,jK.tions 5and 6.That is,its length should be no more than the path length limit L and the distance from the path to any sensor node should be no more than the maximum distance limit d max .Moreover,without exceeding the path length limit L ,the constructed travel path should be as close to the sensor nodes that are not on the path as possible.Fol-lowing these guidelines,in this work,we study multi-path planning (MPP)heuristics based on the idea of seed nodes ,where a partial path is first constructed based on a subset of sensor nodes (defined as seed nodes )and then expanded to consider other non-seed nodes.In what follows,we first address how to construct a sin-gle feasible travel path for the mobile element that will pass by a subset of seed nodes .Then,based on different strate-gies to select the subsets of seed nodes,we propose two MPP heuristics:fixed-K and adaptive-K schemes.4.1Single Path Construction with Seed NodesAlgorithm 1:SinglePathConstructionInput:location of all sensor nodes and basestation,q(a)Node close to an edgeq(b)Node close to a vertexFigure 2.Addition of a node to a pathSuppose that the path to be constructed is P H j(j= 1,···,K)and the distance from P H j to a non-seed node N i is d x.Depending on which point on the path P H j has the minimum distance to N i,as illustrated in Figure2,there are two different cases for expanding path P H j.In thefirst case,as shown in Figure2(a),the closest point to node N i is on one edge of path P H j,which is from node N q+1to node N q+2.If the distance d x is larger than the target distance d t,one virtual node N i will be added such that the distance from N i to the node N i equals d t.Here,we have the target distance d t=d max for the path expansion in Step2which ensures the feasibility of the expanded path. For the further path expansion in Step3,for simplicity,we adopt a greedy approach and set d t=d min.That is,for the selected non-seed sensor nodes,the further path expansion enables the mobile element collect data from such nodes even when they transmit the data with the minimum power level P min.Note that,the location of the virtual node N i can be eas-ily obtained from the position of nodes N i,N q+1and N q+2. After that,the path P H j will be expanded by adding two new edges(one is from node N q+1to the virtual node N i and the other is from N i to node N q+2)while removing the edge from node N q+1to node N q+2.Here,the path length of P H j will increase byΔ=|N q+1,N i|+|N i,N q+2|−|N q+1,N q+2|.The second case is shown in Figure2(b),where the clos-est point on the path P H j to the node N i is at one vertex N q+1.The same as before,if the distance from node N q+1 to vertex N i is d x and larger than the target distance d t,onevirtual node N i will be added and two overlapped edges will be added to the path P H j:one is from N q+1to N i and another is from N i to N q+1.Similarly,the location of the virtual node N i can be determined by setting the dis-tance from N i to N i as d t.And the path length of P H j will increase byΔ=2·|N q+1,N i|(that is,2·(d x−d t)).4.2Fixed-K MPP SchemeFrom Algorithm1,we can also see that the selection of seed nodes is crucial since these sensor nodes are assured to be able to transmit their data at the minimum power level P min when the mobile element follows the corresponding generated travel path.Depending on when and how the seed nodes are selected,wefirst discuss thefixed-K heuristic scheme,where the seed nodes are statically determined for each path to be constructed.Here,to guarantee that each sensor node to serve as a seed node and on at least one of the generated travel paths,thefixed-K heuristic scheme first statically divides the sensor nodes into K subsets(with n K sK.2345051361 R246810.20.3 0.4 0.5 0.6 0.7 2 4 68 10 12 14 16 18 20m a x e n e r g y : K -p a t h v s . s i n g l e p a t number of paths: KN=100:Fixed-K N=400:Fixed-K N=100:Adaptive-K N=400:Adaptive-K0.20.3 0.4 0.5 0.6 0.7 2 4 68 10 12 14 16 18 20m a x e n e r g y : K -p a t h v s . s i n g l e p a t number of paths: KN=100:Fixed-K N=400:Fixed-K N=100:Adaptive-K N=400:Adaptive-K0.20.3 0.4 0.5 0.6 0.7 2 4 68 10 12 14 16 18 20m a x e n e r g y : K -p a t h v s . s i n g l e p a t number of paths: KN=100:Fixed-K N=400:Fixed-K N=100:Adaptive-K N=400:Adaptive-Ka.uniformb.Gaussian-150c.Gaussian-500.050.1 0.15 0.2 0.25 0.3 0.35 2468 10 12 14 16 18 20N S T D f o r n o d e s ’ e n e r g y c o n s u m p t i o nnumber of paths: KN=100:Fixed-k N=400:Fixed-k N=100:Adaptive-k N=400:Adaptive-k0.050.1 0.15 0.2 0.25 0.3 0.35 2468 10 12 14 16 18 20N S T D f o r n o d e s ’ e n e r g y c o n s u m p t i o nnumber of paths: KN=100:Fixed-k N=400:Fixed-k N=100:Adaptive-k N=400:Adaptive-k0.050.1 0.15 0.2 0.25 0.3 0.35 2468 10 12 14 16 18 20N S T D f o r n o d e s ’ e n e r g y c o n s u m p t i o nnumber of paths: KN=100:Fixed-k N=400:Fixed-k N=100:Adaptive-k N=400:Adaptive-kd.uniforme.Gaussian-150f.Gaussian-50Figure 3.The performance of the proposed MPP heuristics versus the number of paths K to be planned;Here,the path limit ratio is 0.8.sensors,the normalized power levels and the corresponding transmit ranges 1are shown in Table 2.In the simulations,we consider a square field of 1000m ×1000m and the base station is assumed to be in the middle of the field.There are 100(or 400)sensor nodes scattered in the field with their locations following uniform or Gaussian distribution.For the Gaussian distribution,the mean for the x and y coordinations of sensors’location is 500and we consider two different variances,50and 150,respectively.For each of these three distributions,we gen-erate 100data sets for the location of the sensor nodes and each point in the results is the average of over 100data sets.For the number of paths,we consider up to 20paths with K =2,5,10and 20for the fixed-K scheme.For the first step in Algorithm 1,we use the Christofides MST heuris-tic [5]implemented using LEDA package [14].Moreover,we define the maximum path length L max as the length for the path that can pass by all the sensor nodes,where the path is also constructed from the MST heuristic.For the pathlength limit L ,we consider the following ratio of δ=LL max:0.40.45 0.5 0.55 0.6 0.65 0.7 0.75 0.8 0.85 0.76 0.78 0.8 0.82 0.84 0.86 0.88 0.9 0.92 0.94m a x e n e r g y : K -p a t h v s . s i n g l e p a t path limit: δFixed:k=2Fixed:k=5Fixed:k=200.40.45 0.5 0.55 0.6 0.65 0.7 0.75 0.8 0.85 0.76 0.78 0.8 0.82 0.84 0.86 0.88 0.9 0.92 0.94m a x e n e r g y : K -p a t h v s . s i n g l e p a t path limit: δFixed:k=2Fixed:k=5Fixed:k=200.40.45 0.5 0.55 0.6 0.65 0.7 0.75 0.8 0.85 0.76 0.78 0.8 0.82 0.84 0.86 0.88 0.9 0.92 0.94m a x e n e r g y : K -p a t h v s . s i n g l e p a t path limit: δFixed:k=2Fixed:k=5Fixed:k=20a.fixed-uniformb.fixed-Gaussian-150c.fixed-Gaussian-500.20.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0.76 0.78 0.8 0.82 0.84 0.86 0.88 0.9 0.92 0.94m a x e n e r g y : K -p a t h v s . s i n g l e p a t hpath limit: δAdaptive:k=2Adaptive:k=5Adaptive:k=200.20.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0.76 0.78 0.8 0.82 0.84 0.86 0.88 0.9 0.92 0.94m a x e n e r g y : K -p a t h v s . s i n g l e p a t hpath limit: δAdaptive:k=2Adaptive:k=5Adaptive:k=200.20.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0.76 0.78 0.8 0.82 0.84 0.86 0.88 0.9 0.92 0.94m a x e n e r g y : K -p a t h v s . s i n g l e p a t hpath limit: δAdaptive:k=2Adaptive:k=5Adaptive:k=20d.adaptive uniforme.adaptive Gaussian-150f.adaptive Gaussian-50Figure 4.The performance of the MPP heuristic schemes versus the path length limit.(Step 3in Algorithm 1)cannot further reduce the energy consumed on the most energy-hungry sensor node.More-over,for the case of 100sensor nodes,the fixed-K scheme performs even worse when more paths are constructed.The reason is again because of the greedy approach adopted in the further path expansion,where it is possible for a sensor node being on the path that it serves as seed nodes but is far away from all other paths.For the adaptive-K scheme,as the number of paths in-creases,the normalized energy consumption for the most energy-hungry sensor nodes generally decreases.That is,longer lifetime for the WSN can be achieved with more paths.However,the improvement becomes less significant as the number of paths is more than 10.When 20paths are exploited,for the case of Gaussian distribution with 150variance,the most energy-hungry sensor node consumes only 25%energy compared to that of the one under the sin-gle path scheme.That is,the lifetime of the WSN can be improved up to 4times.In addition,since only 45%of the sensor nodes are selected as seed nodes when a new path is constructed,for the case of K =2,10%of the sensor nodes do not have the chance to serve as seed nodes and the adaptive-K scheme performs even worse than the fixed-K scheme.Therefore,for better performance of the MPP heuristics,the selection of seed nodes is crucial and each sensor node should serve as a seed node at least once when constructing the K paths.Define the normalized standard deviation (NSTD)for the energy consumption of all sensor nodes as the stan-dard deviation of the normalized energy consumption ra-tio E iE max (iwith variance of50),bothfixed-K and adaptive-K schemes result in large variations on their performance.The bigvariation of thefixed-K scheme,especially for the case of K=20,comes agian from the greedy approach used in the further path expansion,which results in big difference onenergy consumption for the sensor nodes.For the adaptive-K scheme,the abnormality for the case of K=2is due to again the fact that some sensor did not have chance to serve as seed nodes for the two paths constructed.6Related WorkEfficient data collection in wireless sensor networks (WSNs)has been studied extensively[1,7].To address the drawbacks of the multi-hop data forwarding schemes with a static base-station,where the sensor nodes close to the base station will deplete their energy quickly due to their high data transmission activities,mobile base stations have been explored to achieve balanced energy usage among sen-sor nodes[3,4,6,8].In addition,active mobile element has been exploited to visit the sensor nodes and collect data from them via single-hop communication.Shah et al.stud-ied the performance of the mobile element to opportunisti-cally collect data from a sparse WSN based on the random movement model[17].For sensor nodes with limited buffer size,several heuristics have studied to control the mobile element to visit the sensor nodes before the buffer overflow and/or serve the varying data-rates[10,18].More recently,the hybrid approach that consider the combination of multi-hop forwarding and mobile elements has been proposed.Wang et al.show that the best scheme to extend the WSN’s lifetime is to constrain the movement of the mobile element in the vicinity of the base station [22].Considering the delay requirement of the data,Gu et al.studied schemes where urgent data are forwarded to the sensor nodes that are visited by the mobile element more frequently[10].To reduce the length of the travel path for the mobile element,rendezvous points are used as regional collection points and the mobile element collects the data from the rendezvous points[23].Sencar uses a mobile ob-server to collect data,wherefield of interest is divided into regions and the mobile element moves in straight lines in each region and multi-hop forwarding is used to relay pack-ets from distant sensors to the sencar[12].Mobile elements are also used to data collection,storage and retrieval in underwater sensor networks[20].To fur-ther improve the performance,several schemes have been studied to employ multiple mobile elements to improve the efficiency of data collection(e.g.,using load balancing technique)[4,8,11].Different from most of the existing schemes with mobile elements and a single path,our work focuses on planning of multiple travel paths for the mobile element to extend the lifetime of WSNs.7Conclusions and Future WorkFor data collection in wireless sensor networks(WSNs), mobile elements have been deployed to improve the energy efficiency by traversing thefield of interest and collecting sensed data from nearby sensor nodes.However,most of the existing approaches using mobile elements for data col-lection in WSNs normally only plan a single path.In this paper,we study the multiple path planning(MPP) problem for the mobile element.The basic idea is to con-struct multiple paths,which can be followed by the mobile element in turn during data collection in order to balance the energy consumption on individual sensor nodes,thus extending the WSN’s lifetime.We show the intractability of the general MPP problem for constructing K paths and we study heuristic based solutions for constructing a path using seed nodes,which is a subset of the sensor nodes. Based on when and how the seed nodes are selected when constructing the paths,two MPP heuristics are proposed:fixed-K and adaptive-K schemes.The proposed heuristics are evaluated through extensive simulations.The results show that,the life of WSNs can almost be doubled with thefixed-K scheme,even when K=2.For the adaptive-K scheme,the lifetime of WSNs generally increases when more paths are exploited,and up to4times can be achieved with20paths.Moreover,under the adaptive-K scheme,the energy on the sensor nodes is consumed more evenly.For our future work,we will consider cases where a WSN can operate until X%of the sensor nodes die.More-over,adaptive path scheduling for hybrid schemes with multi-hop data forwarding will be studied.References[1]I.F.Akyildiz,W.Su,Y.Sankarasubramaniam,andE.Cayirci.A survey on sensor networks.IEEE Com-munications Magazine,38:393–422,2002.[2]Esther M.Arkin and Refael Hassin.Approximationalgorithms for the geometric covering salesman prob-lem.Discrete Appl.Math.,55(3):197–218,1994. [3]S.Basagni,A.Carosi,E.Melachrinoudis,C.Petrioli,and Z.M.Wang.Controlled sink mobility for pro-longing wireless sensor networks lifetime.Wireless Networks,14(6):831–858,2008.[4]I.Chatzigiannakis,A.Kinalis,S.Nikoletseas,andJ.Rolim.Fast and energy efficient sensor data collec-tion by multiple mobile sinks.In Proc.of the5th ACM Int’l workshop on Mobility management and wireless access(MobiWac),pages25–32,2007.[5]N.Christofides.Worst-case analysis of a new heuristicfor the traveling salesman problem.Technical Report CS-93-13,Carnegie Mellon University,1976.[6]Murat Demirbas¸,Onur Soysal,and Ali S¸aman To-sun.Data salmon:A greedy mobile basestation pro-tocol for efficient data collection in wireless sensor networks.In IEEE International Conference on Dis-tributed Computing in Sensor Systems,June2007. [7]D.Estrin,indan,J.S.Heidemann,and S.Ku-mar.Next century challenges:Scalable coordination in sensor networks.In Mobile Computing and Net-working,pages263–270,1999.[8]S.Gandham,M.Dawande,R.Prakash,andS.Venkatesan.Energy-efficient schemes for wireless sensor networks with multiple mobile base stations.In Proceedings of IEEE GLOBECOM,pages377–381, 2003.[9]Y.Gu,D.Bozdag,and E.Ekici.Mobile element baseddifferentiated message delivery in wireless sensor net-works.In Proc.of the2006Int’l Symposium on on World of Wireless,Mobile and Multimedia Networks, pages83–92,2006.[10]Y.Gu,D.Bozdag,E.Ekici,F.Ozguner,and C.Lee.Partitioning based mobile element scheduling in wire-less sensor networks.In IEEE SECON,pages386–395,2005.[11]David Jea,Arun Somasundara,and Mani Srivastava.Multiple controlled mobile elements(data mules)for data collection in sensor networks.In IEEE Interna-tional Conference on Distributed Computing in Sensor Systems,2005.[12]Ming Ma and Yuanyuan Yang.Sencar:An energy-efficient data gathering mechanism for large-scale multihop sensor networks.IEEE Transactions on Par-allel and Distributed Systems,18(10):1476–1488,Oc-tober2007.[13]A.Mainwaring,J.Polastre,R.Szewczyk,D.Culler,and J.Anderson.Wireless sensor networks for habitat monitoring.In ACM Int.Workshop on Wireless Sensor Networks and Applications,pages88–97,2002. [14]LEDA Algorithm Package.http://www.algorithmic-/leda/index.htm.[15]T.S.Rappaport.Wireless Communications:Princi-ples and Practice.Prentice Hall,1996.[16]Tmote Sky Sensors./products/tmotesky.php,2007.[17]R.C.Shah,S.Roy,S.Jain,and W.Brunette.Datamules:modeling a three-tier architecture for sparse sensor networks.In Proceedings of the First IEEE International Workshop on Sensor Network Protocols and Applications,pages30–41,2003.[18]A.A.Somasundara,A.Ramamoorthy,and M.B.Sri-vastava.Mobile element scheduling with dynamic deadlines.IEEE Transactions on Mobile Computing, 6(4):395–410,2007.[19]G.Tolle,J.Polastre,R.Szewczyk,N.Turner,K.Tu,P.Buonadonna,S.Burgess,D.Gay,W.Hong,T.Daw-son,and D.Culler.A macroscope in the redwoods.In Proceedings of the Third ACM Conference on Embed-ded Networked Sensor Systems,pages51–63,2005.[20]I.Vasilescu,K.Kotay,D.Rus,M.Dunbabin,andP.Corke.Data collection,storage,and retrieval with an underwater sensor network.In SenSys’05:Pro-ceedings of the3rd international conference on Em-bedded networked sensor systems,pages154–165, New York,NY,USA,2005.ACM.[21]W.Wang,V.Srinivasan,and ing mo-bile relays to prolong the lifetime of wireless sensor networks.In Proc.of the11th annual int’l conf.on Mobile computing and networking,pages270–283, 2005.[22]W.Wang,V.Srinivasan,and ing mo-bile relays to prolong the lifetime of wireless sensor networks.In Proc.of the11th annual int’l conference on Mobile computing and networking,pages270–283, 2005.[23]G.Xing,T.Wang,Z.Xie,and W.Jia.Ren-dezvous planning in mobility-assistedwireless sensor networks.In28th IEEE International Real-Time Sys-tems Symposium,pages311–320,2007.[24]W.Zhao and M.Ammar.Message ferrying:Proac-tive routing in highly-partitioned wireless ad hoc net-works.In Proceedings of the The Ninth IEEE Work-shop on Future Trends of Distributed Computing Sys-tems,pages308–314,2003.[25]Dakai Zhu and Ali Saman Tosun.Adaptive pathscheduling for mobile element to prolong the lifetime of wireless sensor networks.SIGBED Review(Work-in-Progress session of RTAS),5(2):1–4,2008.。

无线传感器网络中的多路径路由算法设计无线传感器网络（Wireless Sensor Networks，WSN）是由大量的无线传感器节点组成的自组织网络，通过相互通信和协同工作来实现对环境的监测和数据收集。

在WSN 中，节点之间的通信受限于能量、带宽和传输距离等因素，因此传感器节点的能量消耗和网络生存时间成为网络设计的重要指标之一。

多路径路由算法的设计旨在提高网络的可靠性、生存时间和传输效率，减少节点能量消耗和网络拥塞。

在无线传感器网络中，节点分为两类：源节点和目标节点。

源节点收集环境数据，目标节点接收并处理这些数据。

多路径路由算法的目标是选择多条路径，将源节点的数据传输到目标节点，并在传输过程中平衡网络负载，降低节点能量消耗。

下面将介绍两种常用的多路径路由算法：基于分层的路由算法和基于多路径跳的路由算法。

基于分层的路由算法是一种通过分层组织网络结构来提高网络效率的路由算法。

它将网络划分为多个层次，每个层次分别负责不同的网络任务。

一般来说，分层路由算法包括三个层次：传感器节点、汇聚节点和基站节点。

传感器节点负责数据采集和传输，汇聚节点负责数据聚合和汇总，并将数据转发给基站节点。

在传输过程中，每个层次的节点只与相邻层次的节点交互，避免了全局路由信息的传输和存储，降低了能耗和网络负载。

同时，分层路由算法还可以通过选择具有最佳传输质量和能耗的路径，优化数据传输的效果。

基于多路径跳的路由算法是一种通过选择多个中间节点进行数据传输的路由算法。

相比于传统的单路径路由算法，它可以有效地提高网络的可靠性和生存时间。

在多路径跳的路由算法中，多条数据传输路径的选择是基于节点能量消耗、网络负载和传输质量等因素来进行的。

通过选择多个中间节点，可以将数据同时传输到目标节点，并在传输过程中平衡网络负载，降低节点的单点能耗。

此外，多路径跳的路由算法还可以提高数据传输的容错性，即当某条路径出现故障时，可以自动选择其他可用路径进行数据传输。

"多跳网络"是由节点构造的，包括诸如电脑和移动电话这些设备，这些设备全都用无线 连接到彼此，然后互相可以通过网络转发数据。数据从一个节点跳到另一个节点，直 到抵达目的地。除非所有的节点都发生故障，否则数据总是可用的，如此使得这种网 络拓扑结构可靠且可扩展。

.无线网状网(WMN)技术是面向基于IP接入的新型无线移动通信技术
多径路由算法（协议）简介
—— 2017.6.20
内容

1、背景 2、多径路由算法概述 3、多径路由算法原理 4、展望
1、背景



无线多跳网络（转发节点） 传感器网络(传感器节点) Ad Hoc自组织网络（） 无线Mesh网络 ZigBee


这种网络没有固定的路由器，网络中的节点可随意移动并能以任意方 式相互通信。 每一个节点都能实现路由器的功能而在网络中搜寻、维护到另一节点 的路由

1、背景



特征： 1）无中心和自组织性 2）动态变化的网络拓扑 3）多跳路由 4）受限的无线传输带宽 5）节点能源有限 6）安全性较差 7）移动终端的局限性
1、背景


分类 先应式路由：DSDV（目的序号距离矢量算 法）、WRP（无线路由协议） 反映式路由：AODV（按需距离矢量路由算法） 、DSR（动态源路由算法） 混合式路由：ZRP（区域路由算法）
2、多径路由算法概述
単径路由算法： 优点：简单 缺点：负载不均，性能较低 （没有考虑到路径的公平性，过多的依赖最短路径或者最优
路径；无法很好的获取网络的拓扑信息，导致无法有效的利 用网络的整体信息，进而增加了路由开销；数据发送一般只 利用一条路径，无法实现并行或并发的发送数据）