Real-Time Green Internet of Things

Real-TimeGreen Internet of Things
Dr.MohitBansal Profile Pic
Published Date:26-10-2017
Your Website URL(Optional)
A Secure Path Generation Scheme for Real-Time Green Internet of ThingsThe Internet of Things (IoT) is expected to offer promising solutions to trans- form the operation and role of many existing systems such as transportation sys- tems and manufacturing systems, and enables applications in many domains. The IoT aims to connect different things over networks. The goal of the IoT is to provide a good and efficient service for many applications. A real-time IoT application must react to stimuli from its environment within time intervals dic- tated by its environment. The instant when a result must be produced is called a deadline. Wireless sensor networks (WSNs) have recently been in the limelight for many domains. The IoT can be explained as a general-purpose sensor network. WSNs will constitute an integral part of the IoT paradigm, spanning many differ- ent application areas. Since sensor nodes usually are developed by low-cost hard- ware, one major challenge in the development of many sensor network applica- tions is to provide high-security features with limited resources. In this chapter, we first present a path generation framework with deadline considerations for real-time query processing. To meet the deadline, the framework will assign the time budget to the routing path and then derive a feasible path with the assigned time budget. Then, we present a novel key establishment scheme, named a half- key scheme, that is based on the well-known random key predistribution scheme and DDHV-D deployment knowledge, to provide resource-efficient key manage- ment in wireless sensor nodes with reduced memory space requirements and bet- ter security enforcement. The capability of the proposed approach is evaluated by an analytical model and a series of experiments.A Secure Path Generation Scheme for Real-Time Green Internet of Things  411 16.1 Introduction 16.1.1 Data gathering of IoT The next wave in the era of computing will be outside the realm of the traditional desktop. The Internet of Things (IoT) is a novel networking paradigm which allows the communication among all sorts of physical objects over the Internet 22. In the IoT paradigm, many of the objects that surround us will be on the network in one form or another 7, 41, 73. Ubiquitous sensing enabled by WSN technologies cuts across many areas of modern-day living. This offers the ability to measure, infer, and understand environmental indicators, from delicate ecolo- gies and natural resources to urban environments 3, 25, 54. Recent technological advances have enabled the development of low-cost, low-power, and multifunctional sensor devices. These nodes are devices with integrated sensing, processing, and communication capabilities. Sensor technol- ogy has enabled a broad range of ubiquitous computing applications, such as agricultural, industrial, and environmental monitoring 6, 49, 50, 60, 76. As shown in Figure 16.1, WSN can work as part of the IoT; the collection and pro- cessing of such data leads to unprecedented challenges in mining and process- ing such data. Such data needs to be processed in real time and the processing may be highly distributed in nature 1, 39. However, sensor networks are differ- ent from traditional networking. The sensor network has some physical resource constraints and special properties, thus contributing to the green IoT concept Internet Storage and processing Wireless sensor networks Figure 16.1: System model with multihop communications in the green internet of things.412  Security and Privacy in Internet of Things (IoTs) 11, 87, 98. We need to redesign the management methodology for it. The physical resource constraints of the sensor network include limited bandwidth and quality of service (QoS), limited computation power, limited memory size, and a limited supply of energy. The effective lifetime of the sensor is determined by its power supply. Energy conservation is one of the main system design issues. Ref. 28 shows that the power consumption of each sensor node is determined by the cost of transmission. For example, it requires 5000 nJ of energy to transmit a bit in a sensor node, and it requires 5 nJ of energy to process a single instruction. In scientific settings, WSNs can act as intelligent data collection instruments; one might task the relevant subset of nodes to sense the physical world and transmit the sensed values, using multihop communication paths, toward a base station where all the processing takes place 32. Since the energy cost of pro- cessing data is one order of magnitude smaller than the energy cost of transmit- ting the same data 13, 35, 37, it is more energy efficient to carry out as much processing as possible inside the WSN, as this is likely to reduce the number of bytes that are transmitted to the base station. From the viewpoint of this work, one approach to in-WSN processing construes the WSN as a distributed database, and the processing task injected into nodes for execution is the evaluation of a query evaluation plan (QEP). To optimize QEPs, many mechanisms 24, 52 aim to develop sensor network query processors (SNQPs) that drastically reduce the need for bespoke development while ensuring sufficient low levels of energy consumption as to deliver deployments of great longevity. To support QoS requirement, SPEED 27 and MMSPEED 20 are QoS-based routing protocols that provide soft end-to-end deadline guarantees of packets for WSN. In SPEED, each node keeps information only about its immediate neighbors and utilizes geographic location information to make local- ized routing decisions. The MMSPEED protocol is an extension of the SPEED protocol. It is designed to provide probabilistic QoS differentiation with respect to timeliness and reliability domains. MMSPEED provides multiple delivery speed options for each incoming packet, and each incoming packet is placed into appropriate queues according to its speed class. A multiconstrained QoS multipath routing (MCMP) protocol 31 uses braided routes to deliver packets to the sink according to certain QoS requirements that are expressed in terms of reliability and delay. A message-initiated constraint-based routing (MCBR) protocol 95 is composed of explicit specifications of constraint-based desti- nations, route constraints and QoS requirements for messages, and QoS aware metastrategies. Building on a previously proposed QoS provisioning benchmark model, the energy-constrained multipath routing (ECMP) protocol 4 extends the MCMP protocol by formulating the QoS routing problem as an energy opti- mization problem that is constrained by reliability, play-back delay, and geospa- tial path selection constraints. Moreover, we also need to consider properties of sensor networks: Sensor networks have a large number of sensor nodes. Individual sensor nodes areA Secure Path Generation Scheme for Real-Time Green Internet of Things  413 connected to other nodes in their vicinity via a wireless communication inter- face. Thus, some researchers aim to reduce the impact of interference. The interference-minimized multipath routing protocol (I2MR) 23 aims to support high-rate streaming in low-power WSNs by considering the recent advances in the design of high-bandwidth backbone networks. I2MR tries to construct zone-disjoint paths and distributes network traffic over the paths discovered by assuming a special network structure and the availability of particular hard- ware components. The low-interference energy-efficient multipath routing pro- tocol (LIEMRO) 58, 59 improves the performance demands of event-driven sensor networks (e.g., delay, data delivery ratio, throughput, and lifetime) through construction of an adequate number of interference-minimized paths. LIEMRO utilizes an adaptive iterative approach to construct a sufficient number of node-disjoint paths with minimum interference from each event area toward the sink node. It improves the performance demands of event-driven appli- cations by distributing network traffic over high-quality paths with minimum interference. 16.1.2 Key management of wireless embedded systems In recent years, wireless embedded systems (WEBs) have attracted wide atten- tion due to their suitability for monitoring complex physical-world phenomena 64, 70, 79, 88, 90. WEBs have enabled various applications in many domains such as environment monitoring 53, home and industrial automation 78, 81, cyberphysical systems 61, 71, ubiquitous computing 63, security enforcement and surveillance 83, and military systems 2. The play a vital role in sens- ing, gathering, and disseminating information about environmental phenomena. An instance of a WEB, a WSN, usually consists of a large number of battery- powered wireless embedded sensor systems and some base stations. To secure WEBs, the data transmission must be encrypted and authenticated. Since WEBs are usually developed by low-cost hardware, one major challenge in the deploy- ment of many WEB applications is to provide high-security features with limited resources. The provision of good protection for WEBs is an important issue; there are a lot of research results based on key encryption and management that have been proposed to enhance the security of wireless embedded sensor systems. Besides some excellent works on key encryption 48, 72, 91, 96, key renewal schemes 47, 82, and lightweight authentic bootstrapping 33, many researchers have also proposed effective key management schemes, such as those in 8, 16– 18, 44, 46, 62, 92–94, in the past few years. Tseng 77 proposed an authen- ticated group key agreement protocol for resource-limited mobile devices. A detailed survey of such schemes is provided by Xiao et al. in 86. Eschenauer and Glicor proposed a random key predistribution scheme (RKPS) as an effective solution, in which each wireless embedded sensor node414  Security and Privacy in Internet of Things (IoTs) is randomly assigned a subset of keys from a key pool before deployment 18. The RKPS consists of three phases: key predistribution, shared-key discov- ery, and path-key establishment. If two neighboring nodes share one key, then a direct link may be established. A q-composite random key predistribution scheme 8 extends the random key predistribution scheme by requiring two adjacent communicating sensor nodes to share at least q keys. The rationale behind the extension is to provide a higher resilience for key management. Liu and Ning 44 take advantage of the location information to improve network connectivity. To reduce the storage requirements of wireless embedded sensor systems and resolve the scalability issue, researchers have proposed group-based or deployment-information-based methodologies; for example, 17, 45, 94, 97. Although the probability of two wireless embedded sensor systems sharing com- mon keying information increased, a significant amount of keying informa- tion had to be preloaded to each wireless embedded sensor node, regardless of whether a particular piece of information would be used in the future. Perrig et al. 57 considered a secure architecture in which each node shares a secret key with the base station. Two sensor nodes must use the base station as a trusted third party to set up a new key. Lai et al. 42 proposed a session key negotiation protocol based on a signal master key predeployed at sensor nodes. Wong and Chen 84 considered key exchanging for low-power computing devices, where one of the participants must be a powerful server. 16.2 Real-Time Query Processing in the Green Internet of Things In this chapter, we propose a real-time query-processing framework for the green IoT. Assuming the sensors have a query plan, we then need to derive a feasible query propagation plan to transmit data packets. In real-time applications, the main challenge is to guarantee that the data packet meets its deadline. In such applications, such as a natural disaster monitoring system, the energy consump- tion is of secondary importance. To support real-time queries in the green IoT, the routing path must be adjusted to the packet deadlines and try to minimize energy consumption. 16.2.1 Real-time query processing in the green internet of things The IoT is expected include billions of connected devices communicating in a machine-to-machine (M2M) fashion 12. As for the definition of the IoT: The IoT allows people and things to be connected anytime, anyplace, with anything and anyone, ideally using any path/network and any service 80. It is expectedA Secure Path Generation Scheme for Real-Time Green Internet of Things  415 to offer promising solutions to transform the operation and role of many existing systems such as transportation systems and manufacturing systems, and enables many applications in many domains. The IoT aims to connect different things over its network. The goal of the IoT is to provide a good and efficient service for many applications. A real-time application (RTA) is an application program that functions within a time frame that the user senses as immediate or current 9, 10, 85. Correct system behavior depends not only on the logical results of the computations, but also on the physical time when these results are produced. By system behavior, we mean the sequence of outputs in time of a system. A real-time IoT application must react to stimuli from its environment within time intervals dictated by its environment. The instant when a result must be produced is called a deadline. Many applications are time-critical, such as healthcare, traffic control, and alarm monitoring. As a result, the IoT must collect the data from its things (or sensor networks) before the given deadline. Thus, real-time query processing is needed to provide time-efficient results. Due to advances in sensor technology, sensors are becoming more power- ful, cheaper, and smaller in size. Thus, it has simulated large-scale deployments. From their origin, WSNs were designed, developed, and used for specific appli- cation purposes. In contrast, the IoT is not focused on specific applications. The IoT can be explained as a general-purpose sensor network 21. The IoT would not be targeted to collect specific types of sensor data; rather it would deploy sensors where they can be used for various application domains 55, 56. Thus, WSNs will constitute an integral part of the IoT paradigm, spanning many differ- ent application areas. Note that WSNs can exit without the IoT, but the IoT can- not exist without WSNs. This is because WSNs provide the majority of hardware infrastructure support, through providing access to sensor nodes. In any case, the sensor nodes of WSNs are usually operating with limited battery power, hence the need for energy-efficient techniques to reduce the power consumed, thus con- tributing the green IoT concept 87. In general, the topology of the WSNs can vary from a simple star network to an advanced wireless mesh network. In this work, we focus on the multi- hop wireless mesh network type. Energy efficiency in WSNs has been studied 14, 36, 74. Sensors with data to transmit should relay this data to a single source using multihop. Nodes that do not have data to transmit or that are not relaying the data of other nodes can be put to sleep. Energy efficiency is achieved by reducing the number of active nodes. Without considering the deadline, some researchers proposed a designated-path scheme for energy-balanced data aggre- gation in WSNs 38. The proposed scheme predetermines a set of paths and runs them in round-robin fashion so that all the nodes can participate in the workload of gathering data and transferring them to the sink node. In this chapter, we have taken the time requirements further. Note that data gathered on WSNs would not416  Security and Privacy in Internet of Things (IoTs) transmit directly in the query plan. The realistic paths for gathering data (i.e., the query propagation plan) must meet the deadline and try to minimize the overall energy consumption. 16.2.2 Query processing in the green internet of things Query plan in wireless sensor networks In WSNs, sensors collect and transmit information under limited power and radio bandwidth. Traditional approaches for deploying these applications require months of design and engineering time 75. Sensor query-processing archi- tecture using database technology can, however, facilitate deployment of sen- sor networks, greatly reducing programming effort and time-to-deployment for many such applications. Some query-processing systems such as TinyDB 52, Directed Diffusion 34, and Cougar 89 provide users of WSN applications with a high-level interface to perform queries. Users specify the data of interest through simple, declarative queries, just as in a database system, and the infras- tructure efficiently collects and processes the data within the sensor network. Queries in TinyDB are disseminated through the entire network and collected via a routing tree. The root node of the routing tree is end point of the query, which is generally where the user that issued the query is located. Nodes within the routing tree maintain a parent–child relationship to properly propagate results to the root. Recalling the traditional database, a query plan (or QEP) is a set of steps used to access information in an SQL relational database management system 40, 65–68. This is a specific case of the relational model concept of access plans. Since SQL is declarative, there are typically a large number of alternative ways to execute a given query, with widely varying performances 19. When a query is submitted to the database, a query plan is usually generated by the query optimization module of a database system; it consists of a partial order of the physical operators, such as join, sort, and table scan, of a query for the manipulation of database data. In WSNs, the role of query plan is different form the traditional database. Due to the characteristics of sensor networks, queries need to transfer data to all sensors, and gather data from all sensors. We need to consider the power consumption issues of WSNs. Data gathering on a sensor network should not transmit to the query plan directly. We need to generate a more realistic query plan, a so-called propagation plan that has considered sensor characteristics, to gather sensor data. As shown in Figure 16.2, there are three phases of query data gathering. The first phase is data dissemination from the sink to the sensor nodes. This is usually done through multicasting. Then, the sensor senses objects, and then, the information is retrieved. Finally, the sensor nodes transmit data packets to the sink node based on a query plan. In this phase, sensor nodes usually transmit packets by unicasting.A Secure Path Generation Scheme for Real-Time Green Internet of Things  417 Data dissemination from the Multicasting sink to sensor nodes Sensor sensing Data gathering based on Unicasting query plan Figure 16.2: Three phases of query data gathering. 16.2.3 Network model and problem definition Consider an example where a user asks the sink an urgent question via a declar- ative query, just as in a database system, and then the sink generates a high-level query plan for the query. Finally, the infrastructure conducts a query propagation plan from the query plan to efficiently collect and process the data within the sensor network. In this chapter 51, we study a power-efficient networking problem to gener- ate a data-gathering path that does not violate the given deadline. In this section, we present a network model for research on real-time query processing. Related terminologies and a problem definition are also specified. Query processing and network model The purpose of this research is to generate a data-gathering path of a query plan that does not violate the given deadline D and so that the total energy consump- tion is minimized. We consider a homogeneous WSN. A WSN consists a of set of sensor nodes S =s ,s ,...,s . There is a set of K discrete power levels 1 2 M P =P ,P ,...,P given for sensor nodes, where P P if i j such that a 1 2 K i j higher power level results in a larger range to send data to another sensor node in the WSN. Each power level P is associated with a fixed range R for sig- i i nal transmissions and an energy consumption amount C(P), where R R and i i j C(P) C(P) if P P . i j i j We assume that the sensor nodes can change their power level during the s runtime. The set of edges, denoted as E , includes all possible edges. An edge s e ∈ E represents the connection of sensor nodes s and s . Furthermore, each i, j i j s edge e ∈ E may be associated with a weight e that is equal to C(P), where i, j i, j i a weight denotes the energy consumption of the signal transmission. As pointed out in 28, the energy consumption for a node to transmit signals to another418  Security and Privacy in Internet of Things (IoTs) node increases as the nth power of the distance between the two nodes, for n≥ 2. Assuming that node s transmits k bits of data and the distance to node s is d, i j the energy consumption function is as follows: 2 C (k,d)=e × k× d (16.1) i,j amp A query plan (QP) in the sensor network consists of a collection of physical operators (such as select, join, data acquisition, and aggregate) and a partial order of them. There could be more than one QP pending or executing in the system simultaneously, as shown in Figure 16.3. In many database systems, a query optimizer may have a joint consideration of pending or executing QPs such that the same nodes or subtrees in several QPs are merged, as shown in Figure 16.3 (without the dashed lines and the virtual root node). As a result, a collection of QPs after merging could be considered as a directed acyclic graph (DAG). In addition, we always add a virtual root node for pending/executing QPs such that the input format could be general, as shown in Figure 16.3 (with the dashed lines and the virtual root node). As shown in Figure 16.4, the plan for data gathering could be viewed as q q a query plan QP = (V,E ); each edge e ∈ E represents a need to transfer m,n d(e ) bytes of data from v to v ; for example: d(e ) = 200. The query m,n m n C,D q plan QP has a partial order among E ; for instance, the data transfer of e i, j must be processed before that of e . The data-gathering path at runtime is j,k ep defined as a query propagation plan EP = (V,E ). A subset of EP at runtime ep is shown in Figure 16.5. Each edge e ∈ E represents data units of data i, j i, j Virtual root Join Join Join Merge-join Sort Data acquisition, aggregate-max (X) Data acquisition, Select Select aggregate-average (V) Data acquisition, Data acquisition, aggregate-average aggregate-average (Y) (Z) Figure 16.3: DAG-structured query plan. D t qui reg te-min (W) a a ac sition, agg aA Secure Path Generation Scheme for Real-Time Green Internet of Things  419 500 300 400 D 300 300 300 200 200 200 150 150 Aggregation node 200 C Sensor node 150 Sink Query plan Figure 16.4: A sensor network with a DAG-structured query plan. 300 D Aggregation node j n 300 Sensor node 200 B m r Sink i s 150 k Query plan A C Query propagation plan Figure 16.5: The data gathering path of a query plan. from v to v . Let X→ Y be a path, for example, X−i− j−k−Y be a sequence i j q of paths such that EP=ep,ep∈ E. The function st(e ) represents the start i i i, j time of the path e , and ft(e ) represents the finish time of the path e . As i, j i, j i, j shown in Figure 16.5, A→ D is a path. Both sequence of paths A−B−D and ep A−i−B− j−D are possible for E . Because the relationship between energy A,D consumption and distance is exponential (about 2), it is easy to discover that the energy consumption of the sequence of path A−B−D, with higher power lev- els, is greater than that of path A−i−B− j−D. However, the transmission time of path A−i−B− j−D greater than that of path A−B−D. In a real-time environ- ment, the path A−i−B− j−D might not meet the time constraint. As a result, we need to adjust the power level of the nodes and set up the path to meet the time constraint.420  Security and Privacy in Internet of Things (IoTs) In this chapter, we study the path generation methodology for a query propa- gation plan that we formulate as a real-time query-processing (RTQP) problem, to find a data-gathering path of the given query plan that does not violate the given deadline D and where the total energy consumption is minimized. Problem definition We formulate the real-time query-processing (RTQP) problem explored in this chapter as follows: Problem 16.1 s q Input: A given sensor network SN =(V,E ) with a query plan QP=(V,E ) and a given deadline D. ep Output: A query propagation plan EP=(V,E ). Goal: To find a sequence for execution path EP which starts from v and ends s,t s at v ,(EP transfers data before EP′ ′) such that ft(sink)≤ D and t s,t s =t,t P P q p(e )d(e ) is minimized. i, j i, j i, j e ∈EP j, j This problem is very hard to solve directly. We must convert this problem into two subproblems to reduce complexity. The first one is the time budget assign- ment problem that we summarize in Problem 16.2, and the other is one is the RSP problem that we summarize in Problem 16.3. Problem 16.2 Input: DAG G=(V,E) and a budget B are given. Each edge e ∈ E represents m,n a need to transfer k = tr(e ) bytes of data form v to v with distance d = m,n m,n m n m,n dis(e ). Edge e is associated with a power consumption function p = m,n m,n m,n p(k ,b ,d ). m,n m,n m,n b b Output: DAG GB=(V,E ). Each edge b ∈ E represents the budget of G. m,n ′ ′ b Goal: The critical path of GB is CP = (V ,E )∈ GB. The problem is to P ′ b find an assignment of B such that E ≤ GB, and power consumption P p(k ,b ,d ) is minimized. m,n m,n m,n e∈G Problem 16.3 Input: Given a sensor network SN =(V,E), with a start node s, a target node t, and a deadline D, each edge e ∈ E has an associated positive integral cost c i j i, j and a positive integral delay d . i, j Output: Find a path s to t. The cost (respectively, delay) of a path is defined as the summation of the costs (respectively, delays) along all of its edges. Goal: Find the minimum cost s-t path in SN such that the delay along this path does not exceed a given bound D.A Secure Path Generation Scheme for Real-Time Green Internet of Things  421 The real-time query-processing problem is NP-hard; we prove this as Theorem 16.1: Theorem 16.1 NP-hardness. The RTQP problem is NP-hard. Proof. This arises directly from a special case when we only consider one seg- ment the of query plan and a deadline D. It reduces to an RSP 26 problem. 16.2.4 A path generation framework In this section, we explain the proposed framework. Figure 16.6 shows the frame- work of our mechanism. It contains four major procedures: discovery of the minimal-cost path, discovery of the critical path, budget reassignment, and path regeneration. The first of these is the discovery of the minimal-energy path; we set the nodes on a minimal power level and then apply Dijkstra’s algorithm to find the minimal-energy path of the segments. The second one is the discovery of the critical path; we adapt the above to search for the critical path. The third component is the subdeadline; we apply the above to assign the assignment of a subdeadline of the segments. We assign the subdeadline to each segment with the proportion of the transmission time of the critical path segments. An RSP method is then adopted to derive the new paths. Start Minimal-energy path finding Subdeadline assingment (with jobs, only consider power) Path regeneration Critical path finding Critical path finding Meet N deadline? Y Meet Y deadline? Return path N Return no feasible path End Figure 16.6: The framework of our mechanism.422  Security and Privacy in Internet of Things (IoTs) The main function of propagation plan generation, referred to as Algorithm 16.1, is the major framework of our proposed mechanism. At the beginning, the algorithm assumes that all nodes are set with minimal transmis- sion range. This algorithm will invoke a further algorithm, called MinimalCost− PathFinding Di jkstra() to derive the paths of the query plan with minimal cost (Line 2). This algorithm explores the minimal-cost paths of the query plan using Dijkstra’s algorithm. To assign a feasible time budget, it is necessary to know the longest transmission path. Then, the algorithm invokes Algorithm 16.3 to deter- mine which is the critical path (Line 3). If the derived path violated the deadline, this algorithm would invoke Algorithm 16.4 to reassign the time budget and then generate a new path using Algorithm 16.4. Algorithm 16.2 derives the minimal-cost propagation plan of the given query plan. It is revised from a revision of the well-known Dijkstra algorithm 15. For s q a given sensor network SN =(V,E ) and a query plan Q=(V,E ), the algorithm finds the path with the lowest cost between that sensor node and every other sensor node. It can also be used to find costs of the shortest paths from a sin- gle sensor node to a single destination sensor node by stopping the calculation once the minimal-cost propagation plan to the destination sensor node has been determined. Algorithm 16.3 shows how to find the critical path under the PERT algorithm (Lines 2–8) 69. In this algorithm, we calculate the longest sensor node path to the end of the sink node, and the earliest and latest that each activity can start and finish without making the transmission time longer. This algorithm determines which paths are “critical” (i.e., on the longest path) and which have “total float” (i.e., can be delayed without making the transmission longer). Algorithm 16.4 shows the budget reassignment procedure. As shown in Fig- ure 16.7, a sensor network can derive the critical path via PERT. To save energy, one could reduce the transmission range of some sensor nodes. Thus, we need to know the slack of in time that we can achieve and we can thus assign to the transmission path using Algorithm 16.4 (Line 2). To explore the overall time budget of a path, we need first to explore the paths. In Line 8, Algorithm 16.3 explores the paths via the function ExplorePath() (Algorithm 16.5) that checks paths from parent nodes to leaf nodes. Then, it invokes Algorithm 16.8 (Line 9) to assign the time budget of nodes. After that, it invokes a function that reassigns the segment budget by the budget of the nodes (Line 10). Algorithm 16.5 derives the slack times of query plan segments. Given a sen- s q sor network SN =(V,E ), a query plan Q=(V,E ), and a deadline D, Algorithm 16.5 derives the slack times of nodes from leaf to sink (Line 5). Algorithm 16.6 checks the paths from parent nodes to leaf nodes. Algorithm 16.7 reassigns node budgets; it assigns the new subdeadline of each query plan node, according to the proportion of a segment in the critical path. The new budget of a segment will be reassigned asA Secure Path Generation Scheme for Real-Time Green Internet of Things  423 P i, j NodeTB = NodeTB − × TB currentNode child subsegment Path Finally, we adopt Algorithms 16.9 and 16.10 to generate the execution path. Algorithm 16.1: Propagation Plan Generation s q input : Sensor network SN =(V,E ), query plan Q=(V,E ), deadline D output: Find a set of sequences of execution path EP=EP i, j 1 PROCEDURE: PropagationPlanGeneration(SN, Q) 2 begin 3 EP← MinimalCostPathFinding(SN,Q); 4 CP←CriticalPathFinding PERT(SN,EP); 5 if Finish time of CP violate dead line then 6 BudgetReassignment(Q); 7 PathGenerating(SN,Q); 8 Return path EP; 9 end Let us use a QEP derivation example to illustrate the proposed scheme. Con- q s sider a query plan QP = (V,E ) on a sensor network WSN = (V,E ) as shown q in Figure 16.8a, where each edge in E is a query plan edge. The orange nodes are the query plan nodes. Other nodes are relay sensor nodes. Suppose that the ep objective is to derive a feasible query propagation plan EP=(V,E ). Let wire- less sensor network WSN be taken as an example for the explanation of the algo- rithm. At the beginning, all sensor nodes are set to the minimal power level at which they can be connected. Then, we apply the Dijkstra algorithm (Algorithm 16.2) to derive the minimal-energy paths. After this process, we can derive a query propagation plan QEP as shown in Figure 16.8b. The derived QEP is not equal to QP. This is because the Dijkstra algorithm has discovered some paths consuming smaller amounts of energy than those in the query plan. Then, we can compute the transmission time of a segment of the query plan. The variable ti=the transmission time of a segment of the query plan. For example, t5 is the segment EB. The variable t jk= the transmission time between node j and node k. For example, t5 is the transmission time from node E to node B. It is tEu+tuv+tvB, as shown in Figure 16.8c. Finally, as shown in Figure 16.8d, we can derive all transmission times of QP with the derived QEP. Then, we adopt the PERT algorithm (Algorithm 16.4) to derive the critical path. We set all nodes in a topological order (Line 3, Algorithm 16.3) and fol- low the PERT process (Lines 4–7) to find the path with the largest transmis- sion time of all paths. After that, we can determine the critical path, as shown in Figure 16.9a. The process then returns, the critical path to Algorithm 16.1.424  Security and Privacy in Internet of Things (IoTs) In Line 4 of Algorithm 16.1, we check the transmission time of the critical path. In this example, t = t1+ t3+ t5. If the time of the critical path t is CP CP smaller or equal to deadline D, the derived query propagation plan can satisfy all requirements and the plan is returned. Otherwise, it is necessary to derive a new propagation plan for each segment associated with the critical path. We need Algorithm 16.2: MinimalCostPathFinding Dijkstra s q input : Sensor network SN =(V,E ), query plan Q=(V,E ) output: Find a set of sequence of minimal cost execution path EP=EP i, j 1 PROCEDURE: MinimalCostPathFinding(SN, Q) 2 begin q 3 forall E ∈ Q do q MinimalCostPathFinding Di jkstra(SN,E ); 4 i j 5 Return path EP; 6 end q 7 PROCEDURE: MinimalCostPathFinding Dijk-stra(SN, E ) i j 8 begin 9 initialize signle source(SN,S); 10 S←∅; 11 N← VSN; 12 while N6=∅ do 13 u← ExTract Min(SN); S 14 S← S u; 15 foreach vertex V∈ Ad ju do RELAX(u,v,w,t); 16 Return path EP ; i j 17 end 18 PROCEDURE: ExTract Min(N) 19 begin 20 Return the node that requires minimal transmit distance in the node set of minimal cost; 21 end 22 PROCEDURE: RELAX(u,v,w,t) 23 begin 24 if dv du+ w(u,v) then 25 du← du+ w(u,v); 26 Pv← u; 27 if dv= du+ w(u,v) then 28 if Rv Ru+ r(u,v) then 29 Pv← u; 30 endA Secure Path Generation Scheme for Real-Time Green Internet of Things  425 Algorithm 16.3: Critical Path Finding s q input : Sensor network SN =(V,E ), query plan Q=(V,E ) output: Critical path CP 1 PROCEDURE: CriticalPathFinding PERT(SN, Q) 2 begin 3 Initialize finv← 0; 4 forall vertex v ∈ V, Consider vertices v in topological order do j 5 foreach edge v− w do 6 set finw = max( finw, finv + timew); 7 set DistanceMaxw = max(DistanceMaxw, DistanceMaxv + distancewv); 8 CP←Report PERT Critical Path(); 9 end Algorithm 16.4: Budget Reassignment s q input : Sensor network SN =(V,E ), query plan Q=(V,E ), deadline D output: Time budget of segments TB=T B i, j 1 PROCEDURE: BudgetReassignment(Q) 2 begin 3 SlackComputing(Q); 4 NodeTB ← DeadLine; Sink 5 NodeTB ← 0; VirtualLea f 6 repeat 7 Select the node set of smallest slack into setA; 8 node t← select the biggest node from setA; 9 P← ExplorePath(t); 10 NodeBudgetReassign(P); 11 until all of path have been reassign ; 12 SegmentBudgetReassign(); 13 end to assign subdeadlines to the segments. For example, in this figure, the critical path is E−B−A−Sink. We will apply a two-phase mechanism to deal with the segments, EB, DB, BA, CA, and A−Sink. In our example, the transmission time of the critical path is greater than the deadline. Thus, we follow a two-phase mechanism to derive the query propaga- tion plan. First, we assign the subdeadlines for the segments of the plan. Then, we generate the path for each segment of on the critical path to meet the assigned subdeadline with the RSP algorithm.426  Security and Privacy in Internet of Things (IoTs) Transmission distance After PERT Budget reassignment 18 18 1 17 17 3 2 How to 14 14 14 reassign 14 1 them? 2 13 1 1 12 1 12 1 12 10 12 4 2 10 2 7 7 2 8 2 8 2 10 2 10 3 2 5 5 1 5 5 8 8 4 2 1 4 4 3 3 3 0 0 CP Figure 16.7: Budget reassignment of non-critical-path nodes. Algorithm 16.5: Slack Computing (to decide the time budget reassignment sequence) s q input : Sensor network SN =(V,E ), query plan Q=(V,E ), deadline D output: Slack of each segment SP=SP i, j 1 PROCEDURE: SlackComputing(Q) 2 begin 3 forall vertex v ∈ V do j 4 slack j←∞; node 5 slack virtual Leaf← 0; node 6 SlackNodeComputing(Sink); 7 end 8 PROCEDURE: SlackNodeComputing(node v) 9 begin 10 if node v = virtual Leaf then 11 slack v← 0; node 12 else 13 foreach edge v− w, do slack v= node min(SlackComputing(w)+ SlackEdgeComputing(v,w)); 14 return slack v node 15 end 16 PROCEDURE: SlackEdgeComputing(node v, node w) 17 begin 18 return DistanceMaxw− DistanceMaxv− distancewv; 19 endA Secure Path Generation Scheme for Real-Time Green Internet of Things  427 Algorithm 16.6: Explore Path q input : Query plan Q=(V,E ), basis node output: Find a set of sequences of transmission path TP=T P i, j 1 PROCEDURE: ExplorePath(t) 2 begin 3 c← child(t); q 4 T P← Q ; c,t 5 repeat 6 p← parent(t); q 7 TP← Q ; t,p 8 until parent(t) have already computed ; 9 return T P; 10 end Algorithm 16.7: Node Budget Reassign input : Query plan segment P, time budget basis T B segment output: Time budget of nodes in segment NodeTB=NodeTB i 1 PROCEDURE: NodeBudgetReassign(P) 2 begin 3 repeat 4 Basis← TB ; subsegment P i, j proportion← ; 5 Path 6 NodeTB ← NodeTB − proportion× Basis; currentNode child 7 until all TB of nodes in this subpath have been reassign ; 8 end Algorithm 16.8: Segment Budget Reassign input : Query plan segment P, time budget of nodes TB output: Time budget of segment TB=T B i, j 1 PROCEDURE: SegmentBudgetReassign(Q) 2 begin p 3 forall Q do u,v 4 TB ← NodeTB − NodeTB ; u,v v u 5 end428  Security and Privacy in Internet of Things (IoTs) Algorithm 16.9: Path Generating s q input : Sensor network SN =(V,E ), query plan Q=(V,E ), time budget TB, deadline D output: Find a set of sequences of execution path EP=EP i, j 1 PROCEDURE: PathGenerating(SN, Q) 2 begin 3 forall vertex v ∈ V do j 4 status j← WAITING; 5 edge status j← WAITING; 6 repeat 7 chose the leaf node CP from CP; j 8 EdgeGenerating( j); 9 remove CP from CP; j 10 until CP has no element ; 11 end Query plan node Query plan node Relay sensor node Relay sensor node z z y y A A x x w w C C B B v v E E D D u u (a) (b) Query plan B Query plan t5 tvB v z t1 Query propagation E tEu tuv Query propagation y plan u plan A t2 x w t3 C B t5 t4 v E D u (c) (d) Figure 16.8: An example construction process of a query propagation plan (Part I).

Advise: Why You Wasting Money in Costly SEO Tools, Use World's Best Free SEO Tool Ubersuggest.