CN103200616B - A kind of energy-efficient deployment method setting up Internet of Things network model - Google Patents

Abstract

Translated fromChinese

本发明公开了一种基于物联网技术的网络模型建立和节能部署的方法，属于物联网通信技术领域。本发明提出了基于物联网技术的三层网络架构和网络能耗优化模型。本发明提出的节能部署方法首先根据感知节点与备选中继节点的距离排除与任何感知节点均不能通信的备选中继节点，然后在剩下的中继节点中选出i个，如果它们满足“全覆盖感知节点且与基站形成的拓扑是否是连通图”，则将每段链路的发送节点发送耗能与接收节点的接收耗能之和等价为该段链路的权重，通过改进的Dijkstra方法得到能耗的最小值以及网络的生存时间，将此能耗下对应的网络节点部署方式作为一种最佳节能部署方式。

The invention discloses a method for establishing a network model and energy-saving deployment based on Internet of Things technology, and belongs to the technical field of Internet of Things communication. The invention proposes a three-layer network architecture and a network energy consumption optimization model based on the Internet of Things technology. The energy-saving deployment method proposed by the present invention first excludes the candidate relay nodes that cannot communicate with any sensing node according to the distance between the sensing nodes and the candidate relay nodes, and then selects i among the remaining relay nodes, if they Satisfying "whether the full coverage of the sensing node and the topology formed with the base station is a connected graph", the sum of the sending energy consumption of the sending node and the receiving energy consumption of the receiving node of each link is equivalent to the weight of the link, through The improved Dijkstra method obtains the minimum value of energy consumption and the survival time of the network, and takes the corresponding network node deployment method under this energy consumption as an optimal energy-saving deployment method.

Description

Translated fromChinese

一种建立物联网网络模型的节能部署方法An Energy-Saving Deployment Method for Building an Internet of Things Network Model

技术领域technical field

本发明涉及物联网通信技术领域，尤其针对基于物联网技术的网络模型建立和节能部署策略问题。The invention relates to the technical field of Internet of Things communication, and in particular aims at establishing network models and energy-saving deployment strategies based on Internet of Things technology.

背景技术Background technique

随着通信技术的飞速发展，人们已经不再满足于人与人之间以及需要人参与交互的通信方式，一种更加智能、更加便捷的通信方式为人们所期待。物联网---一种物体、机器间不需要人的参与即可完成信息交互的通信方式便应运而生。物联网（InternetofThings）是一种将所有物件连在一起的智能网络，利用如射频识别（Radio-FrequencyIDentification）、无线通信、实时定位、视频处理和传感技术与设备，使任何智能化物体透过网络进行信息交流。以RFID（射频识别）系统为基础，结合已有的网络技术、传感器技术、数据库技术、中间件技术等，构成一个由大量的读写器和移动标签组成的巨大网络成为物联网发展的趋势。With the rapid development of communication technology, people are no longer satisfied with communication methods that require people to participate in interactions between people and people. A smarter and more convenient communication method is expected by people. The Internet of Things --- a communication method that can complete information interaction between objects and machines without human participation came into being. The Internet of Things (Internet of Things) is an intelligent network that connects all objects together, using technologies and equipment such as Radio-Frequency IDentification (Radio-Frequency IDentification), wireless communication, real-time positioning, video processing and sensing, so that any intelligent object can pass through Network for information exchange. Based on the RFID (Radio Frequency Identification) system, combined with existing network technology, sensor technology, database technology, middleware technology, etc., forming a huge network composed of a large number of readers and mobile tags has become the development trend of the Internet of Things.

然而，在实际生活中，物联网的感知节点大都部署在无人监控的场景中，具有能力脆弱、资源受限等特点，经常有新节点的加入或已有节点的失效，网络的拓扑结构变化很快，网络一旦形成，人很少干预其运行。而且感知节点的无线通信带宽有限，通常仅有几百kbps的速率，电池容量一般不是很大，其特殊的应用领域决定了在使用过程中，不能给电池充电或更换电池，一旦电池能量用完，这个节点也就失去了作用。另外，近年来国家一直在倡导节能减排工作，因此在物联网设计过程中，任何技术和协议的使用都要以节能为前提。However, in real life, most sensing nodes of the Internet of Things are deployed in unmanned monitoring scenarios, which have the characteristics of fragile capabilities and limited resources. New nodes often join or existing nodes fail, and the topology of the network changes. Soon, once a network is formed, there is very little human intervention in its functioning. Moreover, the wireless communication bandwidth of the sensing node is limited, usually only a few hundred kbps, and the battery capacity is generally not very large. Its special application field determines that the battery cannot be charged or replaced during use. Once the battery energy is used up , this node loses its function. In addition, the country has been advocating energy conservation and emission reduction in recent years. Therefore, in the design process of the Internet of Things, the use of any technology and protocol must be based on the premise of energy conservation.

目前，物联网只是处于研究的初步阶段，并没有一个统一的架构，更没有统一的标准可以遵循，对基于物联网技术中节能问题的相关研究也很少，但已有一些研究人员针对无线传感网中的节能问题提出了相关的模型及方法。王新兵教授等人通过等效传感半径来研究传感器节点呈一致分布和泊松分布的WSN（WirelessSensorNetwork）中节点异质性和移动性对网络在覆盖性和能量消耗上的影响，通过实验得出节点的移动性能够减少感知耗能，异质性反而增加了一维随机移动模型的能量消耗，对独立同分布模型没有影响；KonstantinosOikonomou等人研究了链路权重随着相邻节点间的能量水平和链路负载的变化而变化，同时汇点根据一种可扩展的汇点迁移策略可以在邻居节点间移动，该动态汇点调度方式能够减少网络能耗、延长网络时间。OnurSoysal等人研究了WSN中基于MAC(MediumAccessControl)层节能的随机路由机制，提出了一种可以调节节点睡眠/唤醒机制的协议POWERNAP，通过使接收器计算其睡眠/唤醒调度表来解决大量的复杂的调度信息给节点带来的总开销，从而节约了系统的总能耗。虽然以往关于无线传感网络能耗问题的研究对网络能耗进行了优化，但是大都只考虑单纯的能耗约束或者网络生存时间约束或者考虑二者结合的情况，然而系统的造价约束以及链路流量平衡约束也是物联网中不可忽视的因素。同时，由于无线传感网中电磁干扰、空气湿度、温度等因素对路由的传输半径有很大的影响，动态路由机制在户外几乎不能应用，而且传统的AdHoc网络中所有感知节点都可以感知数据以及相互转发数据，这样就很容易造成离基站较近的感知节点承担过重的负载，最终导致网络瘫痪。At present, the Internet of Things is only in the preliminary stage of research, and there is no unified architecture, and there is no unified standard to follow. Related models and methods are proposed for the energy saving problem in sensor network. Professor Wang Xinbing and others used the equivalent sensing radius to study the influence of node heterogeneity and mobility on network coverage and energy consumption in WSN (WirelessSensorNetwork) with uniform distribution and Poisson distribution of sensor nodes, and obtained through experiments The mobility of nodes can reduce the perceived energy consumption, but heterogeneity increases the energy consumption of the one-dimensional random movement model, and has no effect on the independent and identical distribution model; KonstantinosOikonomou et al. studied the link weight with the energy level between adjacent nodes and link load changes, and at the same time, the sink can move between neighboring nodes according to a scalable sink migration strategy. This dynamic sink scheduling method can reduce network energy consumption and prolong network time. OnurSoysal et al. studied the random routing mechanism based on MAC (Medium Access Control) layer energy saving in WSN, and proposed a protocol POWERNAP that can adjust the node sleep/wake mechanism, and solve a large number of complex problems by making the receiver calculate its sleep/wake schedule. The total overhead brought by the scheduling information to the nodes, thus saving the total energy consumption of the system. Although previous studies on energy consumption of wireless sensor networks have optimized network energy consumption, most of them only consider pure energy consumption constraints or network lifetime constraints or a combination of the two. However, system cost constraints and link Traffic balance constraints are also factors that cannot be ignored in IoT. At the same time, due to factors such as electromagnetic interference, air humidity, and temperature in the wireless sensor network have a great impact on the transmission radius of the route, the dynamic routing mechanism can hardly be applied outdoors, and all sensing nodes in the traditional AdHoc network can perceive data And forward data to each other, so it is easy to cause the sensing nodes closer to the base station to bear an excessive load, and eventually lead to network paralysis.

发明内容Contents of the invention

本发明所要解决的问题是：针对物联网规模大、网络节点性能脆弱的特性，提出一种分层的网络架构，综合研究了此架构下节点发送数据时引起的能量消耗约束，链路流量平衡约束，链路最大传输速率约束，系统预算约束以及网络生存时间评价标准，解决了传统的单纯研究能耗问题或者生存时间或者二者结合导致的网络整体性能不能达到最优的问题，并提出一种适用于物联网的静态路由优化算法，解决了物联网技术中能量损耗过多的问题，避免了电磁干扰、空气湿度、温度等因素造成动态路由机制不能很好地适用于大规模物联网。The problem to be solved by the present invention is: Aiming at the characteristics of the large scale of the Internet of Things and the fragile performance of network nodes, a layered network architecture is proposed, and the energy consumption constraints caused by nodes sending data under this architecture are comprehensively studied. Constraints, link maximum transmission rate constraints, system budget constraints, and network lifetime evaluation criteria solve the problem that the overall performance of the network cannot be optimal due to the traditional simple research on energy consumption or lifetime or a combination of the two, and proposes a A static routing optimization algorithm suitable for the Internet of Things, which solves the problem of excessive energy loss in the Internet of Things technology, and avoids factors such as electromagnetic interference, air humidity, and temperature that cause the dynamic routing mechanism to be unsuitable for large-scale Internet of Things.

本发明解决上述技术问题的方案是，一种建立物联网网络模型的节能部署方法，包括步骤，构建一种分层的物联网网络模型包括感知层、中继层和汇聚层，根据各层节点在网络中不同的任务，感知层节点负责感知并发送数据，将感知数据不直接传给汇聚层，而是通过中继层的中继节点转发给汇聚层的基站，感知节点之间互相不传送感知数据，通过这样层层分工又相互协作的方式来达到优化物联网的目的。针对此分层的网络架构提出一种优化模型，该优化模型综合研究了能量消耗约束、链路流量平衡约束、系统预算约束以及网络生存时间评价标准。提出一种算法计算优化模型中四种约束的值及其之间的影响，比较得出一种节能部署方式，其特征在于，首先给定感知节点、基站以及备选的中继节点的数量及位置，计算每一个感知节点与备选中继节点的距离，去掉与任何感知节点均不通信的备选中继节点，其次从剩下的备选中继节点中选出满足条件“能够全覆盖感知节点且与基站形成的拓扑是连通图”的i个中继节点，根据公式确定感知节点单位时间发送耗能，根据公式确定中继节点单位时间接收耗能，根据公式确定中继节点单位时间发送耗能，根据公式确定基站单位时间接收耗能，并将拓扑图中每段链路两端发送节点的发送耗能和接收节点的接收耗能之和等效为该段链路的权重，然后利用改进的Dijkstra算法找出基站到每一个感知节点的最短路径，将求出的所有最短路径的长度相加作为当前网络拓扑的能耗，并根据公式求出该种网络拓扑的生存时间，在改进的Dijkstra算法中若某段链路的流量超过规定的最大链路流量值，则选择次优最短路径以进一步实现链路的流量平衡约束，最后寻找i个中继节点所有可能的网络拓扑的能耗，找出最小耗能值，将此最小能耗对应的所选中继节点、传感器节点及基站的数量和位置的部署作为物联网的节能部署方式。The solution of the present invention to solve the above-mentioned technical problems is an energy-saving deployment method for establishing an Internet of Things network model, which includes the steps of constructing a layered Internet of Things network model including a perception layer, a relay layer, and a convergence layer, and according to the nodes of each layer For different tasks in the network, the sensing layer nodes are responsible for sensing and sending data, and the sensing data is not directly transmitted to the convergence layer, but forwarded to the base station of the convergence layer through the relay nodes of the relay layer, and the sensing nodes do not transmit each other Perceived data can achieve the goal of optimizing the Internet of Things through such a layer-by-layer division of labor and mutual cooperation. Aiming at this layered network architecture, an optimization model is proposed. The optimization model comprehensively studies energy consumption constraints, link flow balance constraints, system budget constraints and network lifetime evaluation criteria. An algorithm is proposed to calculate the values of the four constraints in the optimization model and the influence among them, and an energy-saving deployment method is obtained by comparison, which is characterized in that the number of sensing nodes, base stations and alternative relay nodes and Position, calculate the distance between each sensing node and the candidate relay node, remove the candidate relay nodes that do not communicate with any sensing node, and then select the remaining candidate relay nodes that meet the condition "capable of full coverage Sensing nodes and the topology formed with the base station is a connected graph", i relay nodes, according to the formula Determine the sending energy consumption per unit time of the sensing node, according to the formula Determine the receiving energy consumption of the relay node per unit time, according to the formula Determine the transmission energy consumption of the relay node per unit time, according to the formula Determine the receiving energy consumption per unit time of the base station, and the sum of the sending energy consumption of the sending node and the receiving energy consumption of the receiving node at both ends of each link in the topology graph is equivalent to the weight of the link, and then the improved Dijkstra algorithm is used Find the shortest path from the base station to each sensing node, add the lengths of all the shortest paths as the energy consumption of the current network topology, and according to the formula Find the survival time of this kind of network topology. In the improved Dijkstra algorithm, if the traffic of a certain link exceeds the specified maximum link traffic value, then select the suboptimal shortest path to further realize the traffic balance constraint of the link, and finally find The energy consumption of all possible network topologies of i relay nodes, find the minimum energy consumption value, and use the deployment of the number and location of the selected relay nodes, sensor nodes and base stations corresponding to the minimum energy consumption as the energy-saving deployment method of the Internet of Things .

本发明针对实际工程中部署大规模传感器网所遇到的问题，提出一种适用于物联网的分层网络模型，通过节点层层分工又相互协作的方式来达到优化物联网负载的目的，并通过对模型进行链路流量平衡约束，链路最大传输速率约束，进一步解决了传统AdHoc网络中节点负载不平衡造成的网络过早瘫痪的问题。同时，综合研究了物联网优化的四个主要约束，解决了传统的单纯研究能耗或者生存时间或者二者结合导致的网络整体性能不能达到最优的问题。最后，通过优化算法得出一种最佳的节点部署方式使得网络达到节能部署的效果，由于算法使用静态路由机制，避免了电磁干扰、空气湿度、温度等因素导致动态路由无法在户外大规模应用的局面。Aiming at the problems encountered in the deployment of large-scale sensor networks in actual projects, the present invention proposes a layered network model suitable for the Internet of Things, and achieves the purpose of optimizing the load of the Internet of Things by means of node-level division of labor and mutual cooperation, and By restricting the link flow balance and link maximum transmission rate to the model, the problem of premature network failure caused by node load imbalance in traditional AdHoc networks is further solved. At the same time, the four main constraints of IoT optimization are comprehensively studied, which solves the problem that the overall performance of the network cannot be optimal due to the traditional simple research on energy consumption or survival time or the combination of the two. Finally, through the optimization algorithm, an optimal node deployment method is obtained to make the network achieve the effect of energy-saving deployment. Since the algorithm uses a static routing mechanism, it avoids factors such as electromagnetic interference, air humidity, and temperature, which make dynamic routing unable to be applied outdoors on a large scale. situation.

附图说明Description of drawings

图1是本发明的基于物联网技术的三层网络拓扑结构图Fig. 1 is a three-layer network topology structure diagram based on Internet of Things technology of the present invention

图2是本发明的优化模型图Fig. 2 is the optimization model figure of the present invention

图3是本发明的算法流程图Fig. 3 is the algorithm flowchart of the present invention

具体实施方式Detailed ways

首先我们针对物联网网络模型作如下不失一般性的简化描述：First, we give a simplified description of the IoT network model as follows without loss of generality:

1）用x和y表示欧几里得平面内的两个点，用d(x,y)表示两点之间的距离；1) Use x and y to represent two points in the Euclidean plane, and use d(x,y) to represent the distance between the two points;

2）用集合S={SN₁,SN₂,…,SN_l}表示给定的分布于二维平面内的l个SN（传感器节点），其通信半径记为r>0；2) Use the set S={SN₁ ,SN₂ ,…,SN_l } to represent a given set of l SNs (sensor nodes) distributed in a two-dimensional plane, and its communication radius is recorded as r>0;

3）用集合χ={RN₁,RN₂,…,RN_m}表示分布在二维平面的m个RN（中继节点），其通信半径记为R≥r；3) Use the set χ={RN₁ ,RN₂ ,…,RN_m } to represent m RNs (relay nodes) distributed on a two-dimensional plane, and its communication radius is denoted as R≥r;

4）用集合B={BS₁,BS₂,…,BS_n}表示分布在二维平面上的n个BS（基站），意两个基站之间均可相互通信。4) Use the set B={BS₁ ,BS₂ ,…,BS_n } to represent n BSs (base stations) distributed on a two-dimensional plane, which means that two base stations can communicate with each other.

以下针对附图对本发明所提出的网络模型作具体说明。The network model proposed by the present invention will be specifically described below with reference to the accompanying drawings.

图1所示为本发明的基于物联网技术的三层网络拓扑结构图。FIG. 1 shows a three-layer network topology structure diagram based on the Internet of Things technology of the present invention.

一种基于物联网的分层网络架构，根据节点任务的不同将物联网中节点分布在感知层、中继层和汇聚层，感知层主要包括RFID(射频识别)、传感器、GPS(全球定位系统)、摄像机、激光扫描器等一些感知设备，中继层主要包括一些功能较强的中继节点，汇聚层主要包括接收感知信息的基站，三层网络各节点之间通信特点描述如下：A layered network architecture based on the Internet of Things. According to the different tasks of the nodes, the nodes in the Internet of Things are distributed in the perception layer, the relay layer and the aggregation layer. The perception layer mainly includes RFID (radio frequency identification), sensors, GPS (global positioning system) ), cameras, laser scanners and other sensing devices, the relay layer mainly includes some relay nodes with strong functions, and the convergence layer mainly includes base stations that receive sensing information. The characteristics of communication between nodes in the three-layer network are described as follows:

1.对于任意SN_i∈S，RN_j∈χ，如果存在d(SN_i,RN_j)≤r，则SN_i能向RN_j发送信息；1. For any SN_i ∈ S, RN_j ∈ χ, if d(SN_i , RN_j )≤r exists, then SN_i can send information to RN_j ;

2.对于任意RN_i∈χ，N_j∈χ∪B，如果存在d(RN_i,N_j)≤R，则RN_i能与N_j通信；2. For any RN_i ∈ χ, N_j ∈ χ∪B, if d(RN_i , N_j )≤R exists, then RN_i can communicate with N_j ;

3.对于任意的SN_i∈S，SN_j∈S，即使存在d(SN_i,SN_j)≤r，SN_i和SN_j也不能相互通信。3. For any SN_i ∈ S, SN_j ∈ S, even if d(SN_i , SN_j )≤r exists, SN_i and SN_j cannot communicate with each other.

图2所示是本发明的优化模型图。以下针对模型中的几种约束作具体说明。Shown in Fig. 2 is the optimized model figure of the present invention. The following is a detailed description of several constraints in the model.

以G(V,E)表示一个物联网网络图，其中，V是由网络节点组成的非空集合，|V|表示网络中节点的数量，E是网络中无线链路的集合。由于三层网络模型中感知节点只负责发送数据给中继节点，而中继节点发送数据给基站和相邻的中继节点，所以该三层网络图是一个有向连通图。如果节点i与节点j之间能通信，则称节点j是节点i的邻接节点。N(i)表示节点i的邻接节点集合。用网络连接矩阵A表示节点间的关系，矩阵中的元素定义为：Let G(V,E) represent an IoT network graph, where V is a non-empty collection of network nodes, |V| represents the number of nodes in the network, and E is the collection of wireless links in the network. Since sensing nodes in the three-layer network model are only responsible for sending data to relay nodes, and relay nodes send data to base stations and adjacent relay nodes, the three-layer network graph is a directed connected graph. If node i can communicate with node j, then node j is said to be an adjacent node of node i. N(i) represents the set of adjacent nodes of node i. The network connection matrix A is used to represent the relationship between nodes, and the elements in the matrix are defined as:

${\mathrm{<span><span>a</span>a</span>}}_{\mathrm{<span><span>ij</span>ij</span>}}<span><span>=</span>=</span>\left\{\begin{array}{cc}\mathrm{<span><span>1</span>1</span>}<span><span>,</span>,</span>& \mathrm{<span><span>j</span>j</span>}<span><span>\&Element;</span>\&Element;</span>\mathrm{<span><span>N</span>N</span>}<span><span>(</span>(</span>\mathrm{<span><span>i</span>i</span>}<span><span>)</span>)</span>\\ \mathrm{<span><span>0</span>0</span>}<span><span>,</span>,</span>& \mathrm{<span><span>j</span>j</span>}<span><span>\&NotElement;</span>\&NotElement;</span>\mathrm{<span><span>N</span>N</span>}<span><span>(</span>(</span>\mathrm{<span><span>i</span>i</span>}<span><span>)</span>)</span>\end{array}\right.<span><span>-</span>-</span><span><span>-</span>-</span><span><span>-</span>-</span><span><span>(</span>(</span>\mathrm{<span><span>1</span>1</span>}<span><span>)</span>)</span>$

a_ij为网络连接矩阵中元素，a_ij判断节点i和节点j是否邻接。a_ij is an element in the network connection matrix, and a_ij judges whether node i and node j are adjacent.

本发明综合考虑以下四种约束条件，提出一种优化模型：The present invention comprehensively considers the following four constraint conditions, and proposes an optimization model:

1）能量消耗约束1) Energy Consumption Constraints

由于数据通信的能量消耗远大于数据感应和数据处理的能量消耗，因此本模型只考虑数据通信的能量消耗，即节点发送和接收数据的能量消耗，由自由空间信道模型知：Since the energy consumption of data communication is much greater than the energy consumption of data sensing and data processing, this model only considers the energy consumption of data communication, that is, the energy consumption of nodes sending and receiving data. According to the free space channel model:

节点发送数据耗能：E_tx=(E_elec+εd²)L（2）Energy consumption of nodes sending data: E_tx =(E_elec +εd² )L(2)

节点接收数据耗能：E_rx=E_elecL（3）Node receives data energy consumption: E_rx =E_elec L(3)

式中d为节点间的距离，L为数据量，E_elec表示收发单位数据时电路电子能耗，ε为与节点性能参数。In the formula, d is the distance between nodes, L is the amount of data, E_elec is the electronic energy consumption of the circuit when sending and receiving unit data, and ε is the performance parameter of the node.

根据本发明所提出的三层网络模型的特点，通过以上自由空间信道模型，我们可以分别求出单位时间系统中每个节点的耗能。According to the characteristics of the three-layer network model proposed by the present invention, through the above free space channel model, we can separately calculate the energy consumption of each node in the system per unit time.

单位时间感知节点i的能耗：Perceive energy consumption of node i per unit time:

${\mathrm{<span><span>e</span>e</span>}}_{\mathrm{<span><span>i</span>i</span>}}<span><span>=</span>=</span>\underset{\mathrm{<span><span>j</span>j</span>}<span><span>\&Element;</span>\&Element;</span>\mathrm{<span><span>RN</span>RN</span>}}{\mathrm{<span><span>\&Sigma;</span>\&Sigma;</span>}}{\mathrm{<span><span>a</span>a</span>}}_{\mathrm{<span><span>ij</span>ij</span>}}{\mathrm{<span><span>F</span>f</span>}}_{\mathrm{<span><span>ij</span>ij</span>}}<span><span>(</span>(</span>{\mathrm{<span><span>E</span>E.</span>}}_{\mathrm{<span><span>elec</span>Elec</span>}}<span><span>+</span>+</span>{\mathrm{<span><span>\&epsiv;</span>\&epsiv;</span>}}_{\mathrm{<span><span>1</span>1</span>}}{{\mathrm{<span><span>d</span>d</span>}}_{\mathrm{<span><span>ij</span>ij</span>}}}^{\mathrm{<span><span>2</span>2</span>}}<span><span>)</span>)</span><span><span>,</span>,</span><span><span>\&ForAll;</span>\&ForAll;</span>\mathrm{<span><span>i</span>i</span>}<span><span>\&Element;</span>\&Element;</span>\mathrm{<span><span>S</span>S</span>}<span><span>-</span>-</span><span><span>-</span>-</span><span><span>-</span>-</span><span><span>(</span>(</span>\mathrm{<span><span>4</span>4</span>}<span><span>)</span>)</span>$

单位时间中继节点j的能耗：Energy consumption of relay node j per unit time:

${\mathrm{<span><span>e</span>e</span>}}_{\mathrm{<span><span>j</span>j</span>}}<span><span>=</span>=</span>\underset{\mathrm{<span><span>i</span>i</span>}<span><span>\&Element;</span>\&Element;</span><span><span>(</span>(</span>\mathrm{<span><span>SN</span>SN</span>}<span><span>\&cup;</span>\&cup;</span>\mathrm{<span><span>RN</span>RN</span>}<span><span>)</span>)</span>}{\mathrm{<span><span>\&Sigma;</span>\&Sigma;</span>}}{\mathrm{<span><span>a</span>a</span>}}_{\mathrm{<span><span>ij</span>ij</span>}}{\mathrm{<span><span>F</span>f</span>}}_{\mathrm{<span><span>ij</span>ij</span>}}{\mathrm{<span><span>E</span>E.</span>}}_{\mathrm{<span><span>elec</span>Elec</span>}}<span><span>+</span>+</span>\underset{\mathrm{<span><span>i</span>i</span>}<span><span>\&Element;</span>\&Element;</span><span><span>(</span>(</span>\mathrm{<span><span>BS</span>BS</span>}<span><span>\&cup;</span>\&cup;</span>\mathrm{<span><span>RN</span>RN</span>}<span><span>)</span>)</span>}{\mathrm{<span><span>\&Sigma;</span>\&Sigma;</span>}}{\mathrm{<span><span>a</span>a</span>}}_{\mathrm{<span><span>ji</span>the\; ji</span>}}{\mathrm{<span><span>F</span>f</span>}}_{\mathrm{<span><span>ji</span>the\; ji</span>}}<span><span>(</span>(</span>{\mathrm{<span><span>E</span>E.</span>}}_{\mathrm{<span><span>elec</span>Elec</span>}}<span><span>+</span>+</span>{\mathrm{<span><span>\&epsiv;</span>\&epsiv;</span>}}_{\mathrm{<span><span>2</span>2</span>}}{{\mathrm{<span><span>d</span>d</span>}}_{\mathrm{<span><span>ji</span>the\; ji</span>}}}^{\mathrm{<span><span>2</span>2</span>}}<span><span>)</span>)</span><span><span>,</span>,</span><span><span>\&ForAll;</span>\&ForAll;</span>\mathrm{<span><span>j</span>j</span>}<span><span>\&Element;</span>\&Element;</span>\mathrm{<span><span>\&chi;</span>\&chi;</span>}<span><span>-</span>-</span><span><span>-</span>-</span><span><span>-</span>-</span><span><span>(</span>(</span>\mathrm{<span><span>5</span>5</span>}<span><span>)</span>)</span>$

单位时间基站k的能耗：Energy consumption of base station k per unit time:

${\mathrm{<span><span>e</span>e</span>}}_{\mathrm{<span><span>k</span>k</span>}}<span><span>=</span>=</span>\underset{\mathrm{<span><span>j</span>j</span>}<span><span>\&Element;</span>\&Element;</span>\mathrm{<span><span>RN</span>RN</span>}}{\mathrm{<span><span>\&Sigma;</span>\&Sigma;</span>}}{\mathrm{<span><span>a</span>a</span>}}_{\mathrm{<span><span>jk</span>jk</span>}}{\mathrm{<span><span>F</span>f</span>}}_{\mathrm{<span><span>jk</span>jk</span>}}{\mathrm{<span><span>E</span>E.</span>}}_{\mathrm{<span><span>elec</span>Elec</span>}}<span><span>,</span>,</span><span><span>\&ForAll;</span>\&ForAll;</span>\mathrm{<span><span>k</span>k</span>}<span><span>\&Element;</span>\&Element;</span>\mathrm{<span><span>BS</span>BS</span>}<span><span>-</span>-</span><span><span>-</span>-</span><span><span>-</span>-</span><span><span>(</span>(</span>\mathrm{<span><span>6</span>6</span>}<span><span>)</span>)</span>$

式中ε₁、ε₂分别表示感知节点和中继节点硬件性能参数，E_elec表示收发单位数据时电路电子能耗，F_ij为节点i发送数据给j的数据发送率，d_ij表示节点i与节点j之间的距离，RN、SN、BS分别表示中继节点、传感器节点、基站的集合。In the formula, ε₁ and ε₂ represent the hardware performance parameters of sensing node and relay node respectively, E_elec represents the electronic energy consumption of the circuit when sending and receiving unit data, F_ij is the data transmission rate of node i sending data to j, d_ij represents node i The distance between node j and RN, SN, BS represent the set of relay nodes, sensor nodes, and base stations respectively.

2）链路流量平衡约束2) Link traffic balance constraints

由于节点传输的带宽资源有限，链路上的数据传输速度也是有限的，即链路最大传输速率约束。在本发明的三层网络模型中，中继节点之间可以互相接收和发送数据，所以中继节点之间形成的链路要满足以下约束：Due to the limited bandwidth resources for node transmission, the data transmission speed on the link is also limited, that is, the maximum transmission rate constraint of the link. In the three-layer network model of the present invention, relay nodes can receive and send data to each other, so the links formed between relay nodes must meet the following constraints:

${\mathrm{<span><span>a</span>a</span>}}_{\mathrm{<span><span>ij</span>ij</span>}}{\mathrm{<span><span>F</span>f</span>}}_{\mathrm{<span><span>ij</span>ij</span>}}<span><span>+</span>+</span>{\mathrm{<span><span>a</span>a</span>}}_{\mathrm{<span><span>ji</span>the\; ji</span>}}{\mathrm{<span><span>F</span>f</span>}}_{\mathrm{<span><span>ji</span>the\; ji</span>}}<span><span>\&le;</span>\&le;</span>{\mathrm{<span><span>H</span>h</span>}}_{\mathrm{<span><span>max</span>max</span>}}<span><span>,</span>,</span><span><span>\&ForAll;</span>\&ForAll;</span>\mathrm{<span><span>i</span>i</span>}<span><span>,</span>,</span>\mathrm{<span><span>j</span>j</span>}<span><span>\&Element;</span>\&Element;</span>\mathrm{<span><span>\&chi;</span>\&chi;</span>}<span><span>-</span>-</span><span><span>-</span>-</span><span><span>-</span>-</span><span><span>(</span>(</span>\mathrm{<span><span>7</span>7</span>}<span><span>)</span>)</span>$

式中H_max为链路最大传输速率，F_ij为节点i发送数据给j的数据发送率，χ指中继节点的集合。In the formula, H_max is the maximum transmission rate of the link, F_ij is the data transmission rate of node i sending data to j, and χ refers to the set of relay nodes.

同样，三层网络模型中，感知节点与中继节点之间只有感知节点发送数据给中继节点而形成的链路，中继节点与基站之间只有中继节点发送数据给基站而形成的链路，这些链路需要满足以下约束：Similarly, in the three-layer network model, there is only a link formed by the sensing node sending data to the relay node between the sensing node and the relay node, and there is only a link formed by the relay node sending data to the base station between the relay node and the base station. These links need to meet the following constraints:

${\mathrm{<span><span>a</span>a</span>}}_{\mathrm{<span><span>ij</span>ij</span>}}{\mathrm{<span><span>F</span>f</span>}}_{\mathrm{<span><span>ij</span>ij</span>}}<span><span>\&le;</span>\&le;</span>{\mathrm{<span><span>H</span>h</span>}}_{\mathrm{<span><span>max</span>max</span>}}<span><span>,</span>,</span><span><span>\&ForAll;</span>\&ForAll;</span>\mathrm{<span><span>i</span>i</span>}<span><span>\&Element;</span>\&Element;</span>\mathrm{<span><span>S</span>S</span>}<span><span>,</span>,</span>\mathrm{<span><span>j</span>j</span>}<span><span>\&Element;</span>\&Element;</span>\mathrm{<span><span>\&chi;</span>\&chi;</span>}<span><span>;</span>;</span>\mathrm{<span><span>i</span>i</span>}<span><span>\&Element;</span>\&Element;</span>\mathrm{<span><span>\&chi;</span>\&chi;</span>}<span><span>,</span>,</span>\mathrm{<span><span>j</span>j</span>}<span><span>\&Element;</span>\&Element;</span>\mathrm{<span><span>B</span>B</span>}<span><span>-</span>-</span><span><span>-</span>-</span><span><span>-</span>-</span><span><span>(</span>(</span>\mathrm{<span><span>8</span>8</span>}<span><span>)</span>)</span>$

式中H_max为链路最大传输速率，S、χ、B分别指传感器、中继节点、基站的集合。In the formula, H_max is the maximum transmission rate of the link, and S, χ, and B refer to the collection of sensors, relay nodes, and base stations, respectively.

3）系统预算约束3) System budget constraints

在物联网中，由于基站和中继节点的成本相对较高，所以我们可以尽量部署少量的中继节点及基站来达到减少系统成本预算的目的，其传感器节点、中继节点和基站满足以下关系。In the Internet of Things, due to the relatively high cost of base stations and relay nodes, we can deploy as few relay nodes and base stations as possible to reduce the system cost budget. The sensor nodes, relay nodes and base stations satisfy the following relationship .

0<C_S|S|+C_R|χ|+C_B|B|<W₀（9）0<C_S |S|+C_R |χ|+C_B |B|<W₀ (9)

式中C_S，C_R,C_B分别为感知节点、中继节点和基站的单价，|S|、|χ|和|B|分别代表要部署的传感器节点、中继节点、基站的数量，W₀为系统最大预算。where C_S , C_R , and C_B are the unit prices of sensor nodes, relay nodes, and base stations, respectively, and |S|, |χ|, and |B| represent the number of sensor nodes, relay nodes, and base stations to be deployed, respectively, W₀ is the maximum budget of the system.

4）网络生存时间4) Network lifetime

网络生存时间是物联网中最重要的指标之一。Adhoc网中将网络生存时间定义为网络开始运行到网络中第1个节点能量耗尽的这一段时间，类似的，本发明根据三层网络模型的特点将网络生存时间定义为网络运行到网络中第1个中继节点能量耗尽的这一段时间，因此网络生存时间T与中继节点j的能耗和中继节点的初始能量E₁满足关系：Network lifetime is one of the most important metrics in IoT. In the Adhoc network, the network lifetime is defined as the period from when the network begins to run to the exhaustion of the energy of the first node in the network. Similarly, the present invention defines the network lifetime as the network running into the network according to the characteristics of the three-layer network model. This period of time when the energy of the first relay node is exhausted, so the network survival time T and the energy consumption of relay node j and the initial energy E1_of the relay node satisfy the relationship:

$\mathrm{<span><span>T</span>T</span>}<span><span>=</span>=</span>\mathrm{<span><span>min</span>min</span>}<span><span>\{</span>\{</span>\frac{{\mathrm{<span><span>E</span>E.</span>}}_{\mathrm{<span><span>1</span>1</span>}}}{{\mathrm{<span><span>e</span>e</span>}}_{\mathrm{<span><span>j</span>j</span>}}}<span><span>\}</span>\}</span><span><span>,</span>,</span><span><span>\&ForAll;</span>\&ForAll;</span>\mathrm{<span><span>j</span>j</span>}<span><span>\&Element;</span>\&Element;</span>\mathrm{<span><span>\&chi;</span>\&chi;</span>}<span><span>-</span>-</span><span><span>-</span>-</span><span><span>-</span>-</span><span><span>(</span>(</span>\mathrm{<span><span>10</span>10</span>}<span><span>)</span>)</span>$

即$e_j\&le;\frac{E_1}{T},\&ForAll;j\&Element;\mathrm{\&chi;}---\left(11\right)$Right now$e_j\&le;\frac{{\mathrm{E.}}_1}{T},\&ForAll;j\&Element;\mathrm{\&chi;}---\left(11\right)$

其中e_j由公式（5）求得。Where e_j is obtained by the formula (5).

5）网络的最小耗能作为目标函数5) The minimum energy consumption of the network is used as the objective function

本发明主要研究物联网中的能量消耗问题，目标函数即为网络的最小耗能：$\min (\underset{i\&Element;\mathrm{SN}}{\mathrm{\&Sigma;}}{e}_i+\underset{j\&Element;\mathrm{RN}}{\mathrm{\&Sigma;}}{e}_j+\underset{k\&Element;\mathrm{BS}}{\mathrm{\&Sigma;}}{e}_k)$The present invention mainly studies the energy consumption problem in the Internet of Things, and the objective function is the minimum energy consumption of the network:$\min (\underset{i\&Element;\mathrm{SN}}{\mathrm{\&Sigma;}}{e}_i+\underset{j\&Element;\mathrm{RN}}{\mathrm{\&Sigma;}}{e}_j+\underset{k\&Element;\mathrm{BS}}{\mathrm{\&Sigma;}}{e}_k)$

本发明综合研究物联网的各种约束条件，提出网络优化模型。通过求出的最小网络能耗所对应的网络节点的数量及位置得到一种节能部署方式，并且在算法求解最小能耗的过程中考虑了链路流量平衡约束，进一步改善网络负载以延长网络生存时间，同时考虑了系统的预算约束，通过约束网络节点的部署数量减少系统预算，最后结合网络生存时间来综合评价网络的性能。The invention comprehensively studies various constraint conditions of the Internet of Things, and proposes a network optimization model. An energy-saving deployment method is obtained by calculating the number and location of network nodes corresponding to the minimum energy consumption of the network, and the link flow balance constraint is considered in the process of solving the minimum energy consumption of the algorithm, and the network load is further improved to prolong the network survival. At the same time, considering the budget constraints of the system, the system budget is reduced by constraining the deployment of network nodes, and finally the performance of the network is comprehensively evaluated in combination with the network survival time.

图3所示是本发明的算法流程图。本发明提出的节能部署方法包括：计算每一个感知节点与备选中继节点的距离，去掉与任何感知节点均不通信的备选中继节点，然后在剩下的中继节点中选出i个，判断它们是否能够全覆盖感知节点且与基站形成的拓扑是否是连通图，如果同时满足这两个条件，将每段链路发送节点发送耗能与接收节点的接收耗能之和等价为该段链路的权重，计算能耗的最小值，将此能耗下对应的网络节点部署方式作为一种节能部署方式。以下针对算法中的几个主要步骤作具体说明。Fig. 3 shows the algorithm flow chart of the present invention. The energy-saving deployment method proposed by the present invention includes: calculating the distance between each sensing node and a candidate relay node, removing the candidate relay nodes that do not communicate with any sensing node, and then selecting i from the remaining relay nodes First, judge whether they can fully cover the sensing nodes and whether the topology formed with the base station is a connected graph. If these two conditions are met at the same time, the sum of the sending energy consumption of each link sending node and the receiving energy consumption of the receiving node is equivalent to Calculate the minimum value of energy consumption for the weight of the link, and use the corresponding network node deployment method under this energy consumption as an energy-saving deployment method. The main steps in the algorithm are described in detail below.

步骤1：根据物联网中传感器节点以及可能的中继节点的位置坐标，计算每个可能的中继节点RN_j与每个传感器节点SN_i的距离d_ij，如果d_ij<r（r为传感器节点的通信半径），就将该中继节点RN_j添加到备选中继节点集合，同时将该感知节点SN_i加入到该中继节点RN_j的邻接点集合N(RN_j)。Step 1: According to the position coordinates of sensor nodes and possible relay nodes in the Internet of Things, calculate the distance d_ij between each possible relay node RN_j and each sensor node SN_i , if d_ij <r (r is the sensor communication radius of the node), the relay node RN_j is added to the candidate relay node set, and the sensing node SN_i is added to the relay node RN_j 's neighbor set N(RN_j ).

步骤2：从备选中继节点集合中选出所有可能的i（i是小于备选中继节点数量的整数）个中继节点，并求这i个中继节点的邻接点集合的并集∪N_i(RN_j)，其中N_i(RN_j)表示选出的第i个备选中继节点的邻接点集合，判断∪N_i(RN_j)是否等于感知节点集合，如果相等则表示所选中继节点能够全覆盖感知节点，再根据深度优先搜索判断这i个中继节点和基站形成的网络拓扑是否连通，如果选出的这i个中继节点是感知节点的一个全覆盖，而且选出的中继节点和基站形成的网络图为连通图,则能够使得每个感知节点都能够发送数据给基站，反之则不能。Step 2: Select all possible i (i is an integer less than the number of candidate relay nodes) relay nodes from the candidate relay node set, and find the union of the adjacent point sets of the i relay nodes ∪N_i (RN_j ), where N_i (RN_j ) represents the adjacency set of the i-th candidate relay node selected, judge whether ∪N_i (RN_j ) is equal to the sensing node set, if equal, it means The selected relay nodes can fully cover the sensing nodes, and then judge whether the network topology formed by the i relay nodes and the base station is connected according to the depth-first search. If the selected i relay nodes are a full coverage of the sensing nodes, and The network graph formed by the selected relay nodes and base stations is a connected graph, which enables each sensing node to send data to the base station, and vice versa.

步骤3：得到了中继节点数为i且满足条件“能够全覆盖感知节点且与基站形成的拓扑是连通图”的所有可能的网络拓扑之后，针对每一种网络拓扑，根据公式（3）（4）（5）可得每类节点的能耗值，由于三层网络拓扑是一个有向图，本发明将每段链路的权重等价为发送节点发送耗能与接收节点的接收耗能之和，找出基站到每一个感知节点的最短路径（可利用改进的Dijkstra算法），将求出的所有最短路径的长度相加作为当前网络拓扑的能耗，即为中继节点数为i时的其中一种网络拓扑的耗能，并根据公式（10）求出该种网络拓扑的生存时间，在改进的Dijkstra算法中若某段链路的流量超过规定的最大链路流量值，则选择次优最短路径以进一步实现链路的流量平衡约束。Step 3: After obtaining all possible network topologies with the number of relay nodes being i and satisfying the condition "capable of fully covering sensing nodes and the topology formed with the base station is a connected graph", for each network topology, according to formula (3) (4) (5) The energy consumption value of each type of node can be obtained. Since the three-layer network topology is a directed graph, the weight of each link is equivalent to the energy consumption of the sending node and the receiving energy consumption of the receiving node in the present invention. energy, find the shortest path from the base station to each sensing node (the improved Dijkstra algorithm can be used), and add the lengths of all the shortest paths obtained as the energy consumption of the current network topology, that is, the number of relay nodes is The energy consumption of one of the network topologies at time i, and calculate the survival time of this network topology according to the formula (10). In the improved Dijkstra algorithm, if the flow of a certain link exceeds the specified maximum link flow value, Then select the suboptimal shortest path to further realize the traffic balance constraint of the link.

步骤4：比较步骤3中求出的中继节点数为i时的所有可能的网络拓扑的耗能，得出最小值作为中继节点数为i时的能耗，将此能耗下对应的传感器节点、基站以及已选的中继节点的数量和位置作为本发明所提的节能部署方式。Step 4: Compare the energy consumption of all possible network topologies obtained in step 3 when the number of relay nodes is i, and obtain the minimum value as the energy consumption when the number of relay nodes is i. The number and positions of sensor nodes, base stations and selected relay nodes are used as the energy-saving deployment method proposed in the present invention.

Claims (3)

Translated fromChinese

1.一种建立物联网网络模型的节能部署方法，其特征在于，构建包括感知层、中继层和汇聚层的物联网网络模型，感知层节点负责感知并发送数据，将感知数据通过中继层的中继节点转发给汇聚层的基站，感知节点之间互相不传送感知数据；计算每一个感知节点与备选中继节点的距离，去掉与感知节点均不通信的备选中继节点，从剩下的备选中继节点中选出满足条件：“能够全覆盖感知节点且与基站形成的拓扑是连通图”的i个中继节点，对其中的任一中继节点，根据感知节点单位时间能耗、中继节点单位时间能耗、基站单位时间能耗，并将拓扑中每段链路两端发送节点的发送能耗和接收节点的接收能耗之和等效为该段链路的权重，找出基站到每一个感知节点的最短路径，将所有最短路径的长度相加作为当前网络拓扑的能耗；根据公式：确定感知节点单位时间能耗，根据公式：确定中继节点单位时间能耗，根据公式：确定基站单位时间能耗，由此调用公式计算网络的最小能耗，按照最小能耗对应所选择的中继节点、传感器节点及基站的数量和位置部署为满足节能部署的物联网，其中，ε₁、ε₂分别表示感知节点和中继节点性能参数，E_elec表示收发单位数据时电路电子能耗，F_ij为节点i发送数据给j的数据发送率，d_ij表示节点i与节点j之间的距离，RN、SN、BS分别表示中继节点、传感器节点、基站的集合，a_ij为网络连接矩阵中元素。1. An energy-saving deployment method for establishing an Internet of Things network model, characterized in that, constructing an Internet of Things network model comprising a perception layer, a relay layer and a convergence layer, the perception layer nodes are responsible for sensing and sending data, and the perception data is passed through the relay The relay nodes at the layer forward to the base station at the aggregation layer, and the sensing nodes do not transmit sensing data to each other; calculate the distance between each sensing node and the candidate relay nodes, and remove the candidate relay nodes that do not communicate with the sensing nodes. From the remaining candidate relay nodes, select i relay nodes that meet the condition: "capable of fully covering the sensing nodes and the topology formed with the base station is a connected graph". For any of the relay nodes, according to the sensing node Energy consumption per unit time, energy consumption per unit time of relay nodes, energy consumption per unit time of base stations, and the sum of the sending energy consumption of the sending node and the receiving energy consumption of the receiving node at both ends of each link in the topology is equivalent to the link The weight of the road, find the shortest path from the base station to each sensing node, and add the lengths of all the shortest paths as the energy consumption of the current network topology; according to the formula: Determine the energy consumption per unit time of the sensing node, according to the formula: Determine the energy consumption per unit time of the relay node, according to the formula: Determine the energy consumption per unit time of the base station, and thus call the formula Calculate the minimum energy consumption of the network, and deploy the Internet of Things to meet the energy-saving deployment according to the minimum energy consumption corresponding to the number and location of the selected relay nodes, sensor nodes and base stations, where ε₁ and ε₂ represent the sensing nodes and relays respectively Node performance parameters, E_elec represents the electronic energy consumption of the circuit when sending and receiving unit data, F_ij is the data transmission rate of node i sending data to j, d_ij represents the distance between node i and node j, RN, SN, BS represent A collection of relay nodes, sensor nodes, and base stations, a_ij is the element in the network connection matrix.2.根据权利要求1所述的节能部署方法，其特征在于，更进一步地，中继节点之间形成的链路满足：$\begin{array}{cc}{a}_{\mathrm{ij}}{F}_{\mathrm{ij}}+a_{\mathrm{ji}}{F}_{\mathrm{ji}}\&le;H_{\max }& \&ForAll;i,j\&Element;\mathrm{\&chi;}\end{array},$感知节点发送数据给中继节点形成的链路、中继节点发送数据给基站形成的链路满足：i∈χ,j∈B，其中，H_max为链路最大传输速率，F_ij为节点i发送数据给j的数据发送率，a_ij为网络连接矩阵中元素，满足：$a_{\mathrm{ij}}=\left\{\begin{array}{cc}1,& j\&Element;N\left(i\right)\\ 0,& j\&NotElement;N\left(i\right)\end{array}\right.,$S表示分布在二维平面内的传感器节点集合，χ表示分布在二维平面内的中继节点集合，B表示分布在二维平面内的基站集合。2. The energy-saving deployment method according to claim 1, characterized in that, further, the link formed between relay nodes satisfies:$\begin{array}{cc}{a}_{\mathrm{ij}}{f}_{\mathrm{ij}}+a_{\mathrm{the\; ji}}{f}_{\mathrm{the\; ji}}\&le;h_{\max }& \&ForAll;i,j\&Element;\mathrm{\&chi;}\end{array},$ The link formed by the sensing node sending data to the relay node, and the link formed by the relay node sending data to the base station satisfy: i∈χ,j∈B, where H_max is the maximum transmission rate of the link, F_ij is the data transmission rate of node i sending data to j, and a_ij is the element in the network connection matrix, satisfying:$a_{\mathrm{ij}}=\left\{\begin{array}{cc}1,& j\&Element;N\left(i\right)\\ 0,& j\&NotElement;N\left(i\right)\end{array}\right.,$ S represents a collection of sensor nodes distributed in a two-dimensional plane, χ represents a collection of relay nodes distributed in a two-dimensional plane, and B represents a collection of base stations distributed in a two-dimensional plane.3.根据权利要求1所述的节能部署方法，其特征在于，更进一步地，中继节点j的单位时间能耗满足：$\begin{array}{cc}{e}_j\&le;\frac{E_1}{T}& \&ForAll;j\&Element;\mathrm{\&chi;}\end{array},$其中，T为网络生存时间，E₁为中继节点的初始能量。3. The energy-saving deployment method according to claim 1, wherein further, the energy consumption per unit time of relay node j satisfies:$\begin{array}{cc}{e}_j\&le;\frac{{\mathrm{E.}}_1}{T}& \&ForAll;j\&Element;\mathrm{\&chi;}\end{array},$ Among them, T is the network survival time, and E₁ is the initial energy of the relay node.