# Optimized Quality of Service for Real-Time Wireless Sensor Networks Using a Partitioning Multipath Routing Approach

Authors: Mohammed Zaki Hasan; Tat-Chee Wan
Journal: Journal of Computer Networks and Communications
 (2013)

---

## Abstract

Multimedia sensor networks for real-time applications have strict constraints on delay, packet loss, and energy consumption requirements. For example, video streaming in a disaster-management scenario requires careful handling to ensure that the end-to-end delay is within the acceptable range and the video is received properly without any distortion. The failure to transmit a video stream effectively occurs for many reasons, including sensor function limitations, excessive power consumption, and a lack of routing reliability. We propose a novel mathematical model for quality of service (QoS) route determination that enables a sensor to determine the optimal path for minimising resource use while satisfying the required QoS constraints.
The proposed mathematical model uses the Lagrangian    relaxation mixed integer programming technique to define critical parameters and appropriate objective functions for controlling the adaptive QoS constrained route discovery process. Performance trade-offs between QoS requirements and energy efficiency were simulated using the LINGO mathematical programming language. The proposed approach significantly improves the network lifetime, while reducing energy consumption and decreasing average end-to-end delays within the sensor network via optimised resource sharing in intermediate nodes compared with existing routing algorithms.


---

## Body

## 1. Introduction

A typical sensor network comprises a large number of multifunctional, low-cost, and low-power nodes that are deployed densely and randomly in an environment for monitored sensing to control the environment, perform local processing, and communicate results with a base station that performs most of the complex processing. One of the many challenges concerning wireless sensor networks (WSNs) is how to provide Quality of Service (QoS) parameter guarantees in real-time applications. Several approaches and protocols have been proposed in the literature for QoS parameter support in these types of networks [1, 2]. Energy consumption is considered to be the most important constraint in WSNs because of the low power and the processing factors. These factors reduce the QoS and the lifetime of the network.The primary concern is how to properly use resources (for deriving multimedia content) to provide appropriately shared data among all of the transmission radios while maintaining a proper level of imaging and video data transmission. The main goal is the appropriate use of multimedia resources by properly maintaining a level of optimized QoS, which further depends on the performance of the radio. This goal requires careful processing to achieve optimal end-to-end delay, jitter, and energy consumption, as well as acceptable throughput. Different applications of real-time WSNs have different QoS priorities based on the performance of the transmission radio. For example, some applications, such as event detection (Figure1), might require higher data rates, minimal end-to-end delay, and a long battery lifetime. The requirements depend on the situation for which the application uses the radio service. It is important for each sensor node in the network domain to consider resource allocation as an optimization problem with different potential goals. First, a sensor should attempt to optimize source-based capabilities to maximize its use of resources. Second, a sensor should consider resource utilization from a perspective of need, that is, the hop information. Third, resource allocation should be considered from a global perspective in which the utilization of resources by all of the sensor nodes is considered [3]. Thus, the question raised is how to balance the use of resources and transmission radio to provide optimal QoS parameters as well as to avoid the overuse of resources. This paper proposes the consideration of objective function analysis of adaptive switching of hop-by-hop QoS parameters. It is assumed that the services require a high data rate with a low bit-error probability rate (EPR), which is defined as a factor for improving the amount of information transferred and for understanding such information in light of the design of a waveform under certain channel conditions.Figure 1
Event reporting scenario in WSNs.Fortunately, the calculations of the EPR and the signal-noise ratio (SNR) in most multimedia applications of WSNs are based on path-loss propagation, which impacts QoS parameters. There are many other factors that impact the results of QoS for WSNs, and thus, a combination of optimization and analysis is required. Combinatorial optimization problems are defined as problems that select the best combination out of all of the possible combinations. Most combinatorial optimizations, however, are formulated as integer programming.Integer programming is the process of finding one or more optimal solutions in a well-defined discrete search problem space. Such problems occur in almost all fields of wireless communication. Integer programming is considered to be a perfect commercial optimization modeling system, which is augmented with the capability to restrict certain variables to integer values to investigate the efficiency in solving the related problems. In WSNs, for example, the efficient allocation of multimedia resources is investigated by formulating problems under integer programming to meet the desired objective functions, to satisfy some constraints that are restricted to integer values, wherever other constraints are related to basic resources, such as modulation, channel allocation, and coding.Consequently, to design future major components of WSN devices (nodes) that consume extremely low energy, have low production cost, and operate in high density, it is important to study how to involve integer optimization for an industrial implementation of these severe constraints in terms of operating the sensor nodes for a long time over months or even years. The general problem formulation can be represented as follows [4, 5]:
(1)minx,y,zf(x,y,z),s.t.{gi(x,y,z)≤0,fori=1,…,m,hj(x,y,z)=0,forj=1,…,l,x∈ℛ,y∈{0,1},z∈𝔗,
where f is the objective function, a set of explicit linear constraints defined as gi make up the inequality constraints function, and hj is the equality constraint function. Thus, if z=0, then the problem is referred to as integer programming, whereas if y=0, then the problem is referred to as pure integer programming. The problem is otherwise considered to be a mixed integer programming problem. Lagrangian relaxation (LR) considers only some solution methods in an optimization that cuts across the domains of integer, combinational, and nonlinear programming. Briefly, LR is defined as a procedure that uses the idea of relaxing the explicit linear constraints by bringing them into the objective function with the associated Lagrange multiplier μ [6].To achieve energy and delay constraints in real-time WSNs, we propose a new routing metric for optimizing the link quality between the sensor nodes and minimizing the power consumption and end-to-end delay through the use of simple mathematical modeling. The mathematical model uses mixed integer programming (MIP), which is based on the LR method, to define critical parameters to control the adaptive switching of hop-by-hop QoS routing protocols in the WSNs. The embedded criteria for each objective function that are related to the decision constraints are used to decide which path from the source to the sink will be selected. This paper is organized as follows. Section2 discusses previous studies on related topics. Section 3 discusses the analytical model. Section 3.1 describes the QoS constraint problem definition in real-time WSNs.  Section 3.2 provides more details on wireless channel modeling. Section 3.3 provides more details on the constrained QoS routing modeling for the optimization problem. Section 4 discusses the performance evaluation of the derivation of the mathematical modeling. Finally, Section 5 gives the conclusions and describes future directions.


## 2. Related Studies

Most approaches in wireless sensor networks are to extend the network lifetime while meeting network performance requirements in terms of minimizing the energy consumption. To highlight the novelties of the proposed method for maximizing the lifetime of sensor networks, the results of the proposed model shall be briefly discussed in comparison with two existing models: the upper bounds of the lifetime and the node density control for maximizing lifetime algorithms. The node density control algorithm [7] proposes a new model for minimizing energy consumption that depends on the distribution model of the sensor node in the network to explore the relationship of lifetime and the density distribution manner of the sensor node onto the events area. However, all of the nodes should use the same transmission range, which causes exhaustion in the energy of the nodes. The proposed model analyzes the network lifetime with the node density control approach by deriving the optimum transmission ranges of the nodes. In the upper bound algorithm [8], a new strategy for collaborative information for a routing protocol is proposed. This strategy constructs a realistic network topology model to simulate the gathering and processing of information to investigate the optimal lifetime for some levels of deployment control. In this specific topology, there are several different multipaths that data packets which originate at a specific source node can use to send to the sink node. Therefore, these multipaths also include paths with which the node does not necessarily communicate directly through single hop. Instead, the node can transmit the data packet directly to another node, which is two hops or a multihop away, by spending more energy. Thus, the total number of paths from the source node to the sink grows exponentially as the number of sensor nodes in the network topology increases. However, implementing such a strategy is difficult because it is necessary to determine the exact locations of all of the nodes in the network topology and then to coordinate all of the nodes so that different collaborative strategies are sustained over different periods. The proposed scheme is finds the optimal number of hops without taking into consideration all of the possible multihop paths. Only two modes of communication are used: single hopping and multihopping with an optimum transmission radius. Our scheme is very easy to implement and does not require any exact knowledge of the node locations.One of the many multiconstrained QoS routing challenges is developing a new routing metric. An abundance of routing metrics have been developed for adhoc networks and are usually applied in WSNs. Hop count was one of the earliest routing metrics used, while expected transmission count (ETX) is the most favored routing metric because of its accuracy in estimating the link quality. An extension of ETX, the expected transmission time (ETT), can be viewed as a new metric that considers the influence of the packet size as well as the link quality. Weighted cumulative ETT (WCETT) is designed to account for the diversity of the channels in wireless communication technology, where the nodes use multiple radios at the same time [9]. Several improvements to these routing protocols to achieve different requirements of wireless networks are found in the literature. In [10], the author analyzes the performance of the existing routing metrics to investigate how the network performance requirements, such as the delay and throughput, are met. Improved ETT (iETT) is proposed in [11] as a new routing metric based on ETT to investigate the whole impact of the individual high-loss channel rate on the performance of path routing; the author also considers the MAC layer overheads in calculating the data transmission. A cross-layer of cooperative diversity communication for decision routing is proposed in [12], which studies cooperative communication for the routing protocol to derive a new routing metric that exploits the link quality of each potential relay and considers every individual cooperative transmission scheme. An optimal path from the source to the sink is then selected using the new optimal link metric. Most of the previous existing routing metrics focused on only a single service metric such as energy, reliability, or energy in a single path.In spite of the availability of several routing protocols in WSNs, the design of new routing metrics for multihop communication is still an open research area for many reasons. A few studies consider multiple QoS constraints in multipath routing strategies in sensor networks because the complete and accurate state information is not available as a result of the periodic changes in the link quality and the traffic engineering. However, the hop count and link quality are most frequently used in routing metrics to discover and utilize the improvement in the performance of the routing protocols in the WSNs. In [13], a new QoS-routing protocol applied to multimedia WSNs, called the real-time and energy-aware routing (REAR), is proposed. This protocol chooses delay as a QoS-measurement parameter to construct a cost function for evaluating the energy efficiency. The proposed protocol uses an advanced Dijkstra algorithm to evaluate the structure of the multipath mechanism and to choose the neighbor distance between nodes i and j amid all of the paths for sending real data. To reduce the queue delay for a real-time event packet while monitoring events that occur, a classifier queue model F (Queuej) is used for each node to address real-time and ordinary data and to balance the network lifecycle and save on energy consumption. The protocol suffers from overhead complexity in creating the multipath routing algorithm because the state of the information that is associated with each path is incomplete and inaccurate from the changing traffic and link quality.In [14, 15], a novel real-time approach with a load-distributed routing protocol (RTLD) is proposed. It computes the optimal forwarding hop based on three metrics: the link packet reception rate (PRR), the residual power of the sensor battery, and the packet velocity per single hop. The proposed routing protocol is composed of four functional components: power management, neighborhood management, location management, and routing management. In routing management, there are three subfunctional forwarding processes: metric calculations, mechanism forwarding, and routing problem handling. Power consumption management determines both the transceiver power and the transmission power states of the node by using the MICAz sensor node to develop the RTLD. Uncertainty in the dynamic network topology and traffic changing caused this protocol to elaborate the energy consumption profile for diverse levels of duty cycle of the sensor network, which is used to derive the trade-off between the energy conservation and the quality of service.The ReInForM protocol as described in [16] employs probabilistic flooding to deliver the information awareness packet and service at desired priority levels of reliability at a proportional cost for sensor networks. This protocol operates through the proposed dynamic and randomized multipath forwarding mechanism to forward multiple copies of the same information packet in multipath routing according to the decision of the source, to route the packets toward the sink. The routing mechanism is based on local knowledge of network conditions, such as channel error, hops counting to sink, and out-degree. Information on the network conditions is stored on the head of the header of the packets without requiring any data caching at any sensor node, while using the dynamic packet state (DPS) method, which causes an increase in the probability of information delivery. This protocol is not designed specifically for real-time or multimedia traffic; therefore, it does not consider the delay deadlines of the packet when selecting the multiple paths. A chosen path might not be able to meet the deadline; yet it will duplicate the packets that might cause a high cost of energy consumption and the occupation of useful channel bandwidth utilization without improving the system performance.In [17], the network coding-reliable multipath routing (NC-RMR)protocol for WSNs is presented. The NC-RMR protocol employs the computational method of paths and next-hop node selection as in the ReInForM protocol, but it is different from ReInForM. The first difference is in avoiding the redundancy of copies of packets; NC-RMR applies the network coding mechanism in delivering packets through a multipath from source to sink. Second, to increase the level of reliability, the NC-RMR protocol employs a hop-to-hop mechanism to establish a disjoint and braided multipath-routing protocol. The successful delivery packet probability is expressed as pk=(1-e)k, where k is defined as the number of successful hops toward the sink. The computation of reliability is performed using the Bernoulli distribution, specifically, ∑i=0mCMi*(1-pk)M-i*pki. The NC-RMR protocol includes a load balance that is implemented by the braided multipath and optimal next hop-to-hop node selection. The disadvantage of this proposed scheme is the suggestion that node-disjoint multipath routing conserves energy, but the selection of the path could have more hops to reach the destination. Additionally, the system might not have the ability to adapt quickly for a time-varying link quality condition. Conversely, NC-RMR saves 67% of the overheads in terms of the maintenance and complexity, which makes it capable of a 50% higher resilience to node failure.Unlike an end-to-end (E2E) QoS scheme that influences the performance, another soft QoS mapped into links on a path is provided based on local link state information of wireless ad-hoc and sensor networks, for example, critical bandwidth ratio. Stochastic integer programming addresses the E2E soft QoS problem in a rigorous way. Consequently, a model that is based on probability exploration to provide E2E soft-QoS parameters under multiple constraints for a multipath-routing protocol (MCMP) is proposed in [18]. The authors suggest that a distributable manner is the main requirement to achieve a high level of E2E soft-QoS of the selection path. The partition is obtained from the hop requirements for both the additive delay and the multiplicative reliability, which is formulated as Lid=(BoundedDelay-Delaynodei)/Hopcount, where the Hopcount is a counter of the hops from the source to the sink, Delaynodei is the value of the delay involved for processing data at nodei, and BoundedDelay is the definition of the total delay from the source to the sink. Reliability formation is formed as Lid=ReiHopcount, where Rei is defined as the reliability requirements that are assigned to the path through nodei. In [18], both the delay and the reliability constraints are provided, and in [19], a third constraint is added, namely, the energy constraints. Thus, the energy, delay, and reliability become competitive constraints in WSNs, which generates a tradeoff between the single-path and multipath routing deployments, where minimizing both the delay and energy constraints and the maximizing reliability are at stake. Although the proposed model addresses the issues of multiconstrained QoS in WSNs through a combination of the resource of multipaths for traffic flow, it does not consider accounting for the predictability of the network for topology to minimizing the energy consumption and the delay, respectively. Our proposed model considers the predictability of the network topology to search the multipaths and choose one of them.The author of [19] extends the model proposed in [18] into a new model that is called energy constrained multipath (ECMP), which is generated by building on geospatial energy propagation to formulate QoS routing in WSNs. This model is expressed as  w(Si,Si+1)=ε1+ε2*∥xsi-xsi+1∥n, where Si,Si+1∈Link for i=1,2,…p is an ordered pair of two sensor nodes in the path and  ε1=ε11+ε12, where ε11 is defined as the energy per bit consumed in the transmission mode by Si and ε12 is defined as the energy per bit consumed in the receiving mode by Si. The location ∥xsi-xsi+1∥ of each pair of sensor nodes is defined as the Euclidean distance. The concept of geospatial energy propagation depends on the Pythagorean theorem, which shows whether the distance between the two sensor nodes is larger than another link. The Pythagorean theorem finds that the energy transmission between two sensor nodes is shared with the source; thus, the choice of other links that connect a sensor with higher energy transmission to forward the packets leads to energy efficiency. The MCMP model proposes an arbitrary selection link more accurately with a random choice if it is the optimal selection for minimizing the energy consumption. Thus, the ECMP model attempts to find a subset from a set of sensor nodes that have a lower expected energy transmission, while meeting the QoS requirements by delivering packets to the sink. The ECMP model searches for the subset of multipaths from the source to the sink that satisfy the requirements of the data source for the QoS and the total energy of transmission. The concept of this protocol is inspired by geospatial energy propagation, which depends on the Pythagorean theorem and leads to the overhead message control problem. Unlike our proposed mathematical framework, which is borrowed from mixed integer programming (MIP) and is based on the LR method, we define critical parameters to control the adaptive switching of hop-by-hop QoS routing protocols in WSNs. At the same time, the ECMP model uses the optimization method borrowed from the zero-one mathematical framework [5].A novel cross-layer cooperative communication has been studied. The transparency behavior between the physical layer (PHY) and MAC is proposed in [20] to improve the overall network performance by exchanging information between these protocol layers. The author aimed to develop a cross-layer protocol for an efficient routing algorithm by including joint energy consumption and green routing at the network layer, using an optimization scheme based on adaptive modulation at the PHY and using suitable powersaving with a sleep mode mechanism at the MAC. The proposed routing algorithm selects the optimal multihop path based on the battery energy level by the apativate modulation and dynamic power transmission of each sensor node.Usually, previous improvements in routing protocols must applied be to address the computational complexity problem without designing an analytical model for the network performance because of the multiconstrained QoS parameters faced with time complexity and/or space complexity. Unlike previous approaches, the proposed model formulates the problem of finding a path subject to additive multiconstraints routing in an analytical way. This model is performed by designing a new routing for traffic engineering that implements capacity provisioning based on the partitioning of end-to-end QoS parameters by using MIP.


## 3. The Proposed Analytical Model

The proposed methodology uses MIP, which is based on the LR method, which defines a critical parameter for solving nondeterministic polynomial time problems. The method is motivated by the need to find a plan to increase the capacity of multiservice Internet protocol networks, which have been developed over recent years, to account for the new technologies and mechanisms that enable QoS parameters, such as the delay, jitter, and throughput, with different constraints to be satisfied, to guarantee the optimal resource allocation for the task. There are two main types of multiservice differentiated service architecture (DiffServ) and integrated service architecture (IntServ) [21]. These two types of services are provided for three main QoS traffic mechanisms: traffic control, resources management, and traffic engineering [22]. We briefly state these categories, where there are some implications that should be considered for designing a new routing metric. Traffic control encompasses all of the mechanisms for handling and forwarding the packets to both the nodes and the paths of the network. Resource management refers to mechansims that manage access to network resources to prevent service degradation from traffic overload. Traffic engineering is defined as a process of network optimization and is considered to be the main concept in routing optimization. The inspiration for the methodology of multiservice for traffic engineering is to design a new routing metric that implements capacity provisioning based on the partitioning of end-to-end QoS parameters by collecting the information between a source node and the next hop neighbor periodically in the network. The proposed framework can be stated as follows.(1)
Given the network topology, the objective functions, the availability of link quality, the traffic demand, and end-to-end QoS constraints.(2)
Minimize the objective function using the link quality for each partitioned link between two paired nodes.(3)
Subject to the satisfaction of all of the partitioned links between two paired nodes, the traffic demands, and end-to-end QoS constraints.The proposed scheme can be performed by means of a two-phase procedure for each end-to-end QoS parameter. The first phase precomputes the objective function for optimizing the adequate path, which depends on routing information and the link quality. The second phase precomputes the constraints by using the MIP model to partition the adequate path from a predetermined set of optimal paths when the connectivity between two pair sensor nodes occurs with an appropriate link quality. We use such a method because one-hop link metrics are easy to acquire. Figure 2 illustrates the partitioning. Our goal is to determine the optimal path that satisfies all of the QoS requirements for an efficient  routing protocol over a multihop route.Figure 2
Partitioning QoS requirements at all down-stream hops on demand in the network.


### 3.1. The Problem Formulation

The problem of energy efficiency for object tracking in WSNs can be modeled with a directed network topologyG=(V,E), as shown in Figure 2, which is composed of sensor nodes that are distributed according to a two-dimensional Poisson distribution with respect to the density, where |V|=n is the number of sensor nodes and |E|=l denotes the set of links in the network. Each node is characterized by a transmission range. Moreover, each sensor node enters a sleep state once there is no ongoing transmission; otherwise, it enters a wakeup state. The existing link between two sensor nodes is defined as  e=(si,si+1) from node si to node si+1, where i=1,…,n.  Each link e∈E is characterized by two integer values: the energy consumption and the delay. A decision variable xj is defined as a variable that has the value 1 if there is connectivity between two sensor nodes, and 0 otherwise.


### 3.2. Wireless Channel Modeling

Unlike in wired networks, sensor nodes in wireless networks send information to each other by sharing common media. The key is how to organize the sensor nodes in the network topology to obtain as much as possible real-time information, such as video transmission over multi-hop communication scenarios as in event detection.  In general, there are two models for these common scenarios: (1) a channel-modeling-based point of view, in which the communication topology is a single communication channel model, and the key is to enable multiple signals to occupy the model, and (2) a packet-reception-based point of view for the mechanism to access the media where any simultaneous transmission will cause collisions. The channel-modeling-based perspective considers an approach that almost uses wireless mobile communication, while the packet-reception-based point of view has been investigated in computer networks, as in wireless random access networks [23].Designing real-time routing protocols for WSNs involves both approaches. The link quality is applied in wireless communication and considers the following factors in improving the PRR: the energy consumption, QoS parameters, and energy efficiency. The received signal envelope can be in several different modularities, for example, it can be modeled as Rayleigh fading. Given the modulation and coding schemes, the channel fading characteristic results in different PRR values because of radio wave reflection, refraction, and scattering, which give rise to the phenomenon known as wireless channels with multipath fading [24]. In this approach, the transmission channel exhibits the common characteristics of a time-varying channel; the statistical parameters that define the transmission channel vary slowly with respect to the interval of successful data packet transmission, which leads to complex performance analysis for the upper-layer protocols [25].Consequently, the alternative solution is to approximate and model the transmission medium fading channel as a discrete memoryless finite-state two-state Markov chain that is widely acknowledged as a reasonably accurate and mathematically tractable approach, which was first employed in [26], as shown in Figure 3, and is characterized by a specific EPR. This two-state modeling is proposed as a probabilistic process by using a Bernoulli distribution for distributing consecutive packets and the signal-bit-error correction mechanism into a finite number of level-crossing rates for SNR, denoted as Γto derive a mathematical model for the link quality, which is called a good channel and a bad channel, denoted as 0 and 1, respectively. Consider mapping a finite number of level-crossing rates as the tth state, in which an SNR that falls between Γgt and Γgt+1 represents a good state g. The bad channel state b represents a link quality of the channel propagation situation in which achieving a proper reception of the data packets is extremely difficult. Each state is associated with transition probabilities Pgb, where g,b∈{0,1} and ∑Pgb=1 toggle from state g to state b, which is dependent on the characteristic of the propagation environment, the transmission modulation scheme, and the detection technique, implemented at the receiver in which the SNR falls. In other words, the channel transition probability matrix is
(2)channeltransition=[p00p01p10p11]=[p1-p1-EPREPR].Figure 3
Two-state Markov chain transmission channel model.For a Rayleigh fading channel with additive white Gaussian noise, the received instantaneous SNRΥ is exponentially distributed as
(3)p(Υ)=1Υ0exp(-ΥΥ0),
where Υ0 is the mean of the received SNR.The steady-state probability of good channel stategt is given by
(4)π0=∫ΓgtΓgt+1p(Υ)dΥ=exp(-ΓgΥ0)-exp(-ΓgΥ0).This mathematical model is used to derive the relationship between PRR and SNR and evaluates the trade-offs between them. For example, when the SNR value is greater than 20~50 dB, PRR is almost 100%. A higher transmission power results in a higher signal to interference and SNR along the selected path but decreases the energy efficiency of the sensor node. Therefore, we determine the appropriate transmission power to reach the level-crossing rate of SNR at an appropriate value for a desired PRR value using a mathematical model that computes the optimal number of hopsn for the source to the sink. To derive the transition probabilities for consecutive packets p that are assumed to be probabilistic process, assume Pi to be a random variable that is equal to 1 if the ith packet is successfully received and 0 otherwise; then, let the Pi be independent and identically distributed for i=1,…,p. The expected value of Pi, E(Pi) is equal to the probability that packet i is successfully received, that is, Ps(i), so the average number of correctly received packets in the p transmission is
(5)PRR=1p∑i=1pPi,
where i=1,2,3⋯p.Thus, for real-time applications in WSNs in whichp is large, PRR can be closely approximated by the probability of a correctly received packet E(Pi)  [27–29]. For a quality link, suppose that each sensor node knows the link quality of its neighboring nodes through pe, which is represented as EPR [17]. All of the EPR calculations depend fundamentally on the SNR at the receiver. Therefore, the receiver must estimate the noise power and the power received because of the path-loss propagation. With this knowledge about the modulation scheme, the transmitted power, the path-loss propagation, and the noise floor, the receiver power and noise power for the EPR can be estimated. Thus, the PRR can be closely approximated for multi-hop communication by
(6)PRR≅E(Pi)=(1-pe)hop.
Some companies supply the EPR value for developers. For example, the Zigbee implementation on the MC13213 chip produced by the FreeScale Semiconductor Company [30] has a basic function of MLMELinkQuality that developers can use to obtain the current EPR. The link quality of a hop from the source to the sink is represented by EPR; thus, the value of the transmission of packets on each hop from the source to the final sink can be defined as an independent event that circumvents the complexities of retransmission. Furthermore, there is no coding. Thus, the single-bit-error rate leads to a packet error. The successful delivery probability for one packet for each hop is [15]
(7)PRR=(1-pe)hop,
where
(8)pe=1π0∫ΓgtΓgt+1(1-12exp-(p(Υ)/2)*(1/0.64))ρ8fdΥ.
For each correctly received packet, f data frame bits are received over a time period of
(9)fbitrate,
where bitrate = number  of  bits  per  symbol · symbolrate.Furthermore,(10)SNR=Pt-PL(d)-Sr,
where Pt is the transmitted power in dB and Sr is the sensitivity of the receiver in dBm. Finally, PL(d) is represented as
(11)PL(d)=PL(d0)+10γlog(dd0)+Xα,
where d is the total distance between the source and sink, d0 defines a distance reference between the two nodes, γ is the path loss exponent (which depends on the specific propagation environment), and Xα is a random variable drawn from a Gaussian distribution with a zero mean and a standard deviation of α units of dB, and ρ as the encoding ratio. The initial tests on the performance show the optimization of minimizing the energy consumption and the end-to-end delay pressure exerted by increasing the probability of the link estimation.


### 3.3. Multiconstrained QoS Multipath Routing in WSNs

Energy efficiency is considered to be the most important issue upon which the performance of the routing algorithm for WSNs depends. Apparently, the single-path multipath routing algorithm consumes lower energy than the multi-hop multipath because the energy that is required to transmit a packet over multiple paths is approximately twice as great as the energy required to transmit the same packet over a single path. Nevertheless, the multipath strategy could be used as a solution in most optimization routing methods in real-time WSN applications when it is desirable to set up multiconstraints QoS parameters such as energy consumption, reliability, and delay because of increasing the reliability of the data packet delivery and decreasing the average of the data packet delivery along the multipath available from the source to destination. Therefore, energy consumption, average delay, throughput, reliability, and other parameters are defined as QoS competitive constraints by different standardization stack layers (physical, MAC, network, and transport) in WSNs. These QoS parameters meet a trade-off between the resource limitations and multipath routing strategy, to ensure that the QoS requirement is guaranteed in the sensor networks.QoS parameter performances for all of the section layers are not the same and influence other QoS parameter performances. Therefore, any performance degradations of one parameter can degrade the performance of other parameters. Thus, the relationship between the QoS parameters in different layers in a typical communication stack must be defined to specify the architecture in which the QoS requirements could be provided in sensor networks. Figure4 illustrates a simplified proposed QoS model framework for WSNs. The proposed model enables the physical layer to coordinate the behavior of the MAC and the network layer to find optimal multipaths from the source to sink subject to two or more QoS competitive constraints. The application layer might have end-to-end delay as a QoS requirement, which will be coordinated in the network layer and the MAC. The proposed model used a physical layer to determine the link quality to the MAC and a network for metric routing. The proposed metric routing is used as a reference for the scheduling in the MAC and to control the adaptive switching of hop-by-hop QoS routing protocols in the network layer. Additionally, the duty cycle of the sensor node (wakeup/idle/sleep/transmit/received) action at the MAC layer will coordinate the optimization performance of the multipath routing protocol.Figure 4
The proposed QoS model framework for WSNs.


#### 3.3.1. Energy Optimization Modeling

In this section, we derive a new mathematical model to minimize the power consumption, and then, we determine the optimal number of hops that are derived. There are two categories of techniques for delivering the report on event detection to the base-station or sink: (i) the former model, with a direct transmission to the sink, that is, a single-hop transmission, and (ii) multi-hop transmission, with the event reported based on multi-hop relaying between the intermediate nodes and the sink.Figure5 shows the one-dimensional linear array of sensor nodes in networks that can be used to represent most real-time wireless sensor applications, such as traffic monitoring and congestion control. This one-dimensional linear array method helps us to study the energy consumption in various multi-hop scenarios and to analyze and optimize the radio link for a specified topology. The analyzed topology assumes that the space between the sensors can be represented as equidistant sensor nodes.Figure 5
Linear energy consumption modeling.The energy model for sensor nodes in wireless networks is defined by assuming that a sensor node uses its power to carry out three primary functions: acquisition, communication, and data processing. The communication function consumes more energy than the other two functions because it includes two suboperations: energy transmission and energy reception. In most wireless sensor applications, the most commonly used energy model is called the first-order radio model. According to this model, the radio consumes an amount of energyEtx, which is defined below, to transmit p bitsof information over a specified distance d; the energy is defined for two categories of the transmission model [31]. Definition of these radio transmission model is listed in Table 1:
(12)Etx(p,d)={p·Eelec+p·εfs·dαforonepathtransmission,p·Eelec+p·εmp·dαformultipathtransmission,
where the amount of energy to receive p bits of information is
(13)Erx(p)=p·Eelec.
The amount of energy that is required to forward p bits of information is
(14)Etx(p,p)={2p·Eelec+p·εfs·dαforonepathtransmission,2p·Eelec+p·εmp·dαformultipathtransmission.
To transmit p bits of information over n hops along the selected path, the total energy required is
(15)Energysisi+1=p{∑i=1n[2·Eelec+εmp(di)α]}.
If we denote the energy dissipation as Pdiss, then to minimize the energy consumption, we formulate the optimization problem as
(16)Pdiss≥p{Etx+Erx}.
For our optimization problem, we define the previous equation as the objective function that we use to minimize the energy consumption for the linear array. The two variables that must be defined are the number of hops and the intermediate distance between two sensor nodes along the selected path. Thus, we can rewrite the equation as
(17)MinEnergysisi+1=p{∑i=1n[2·Eelec+εmp(di)α]}xjaljsisi+1.
Then, we must define the corrected constraints, which we obtain from both the number of hops from the source to the final sink and the definition of the intermediate distance between two sensor nodes. Because our application involves realistic WSN environments, it is necessary to find the optimal number of hops and the corresponding intermediate distance. For a fixed intermediate distance,
(18)∑i=1hopdi=d.
We must minimize the value of Esisi+1 when r1=r2=⋯=rn=totaldistance/numberofhops. We can obtain the optimal theoretical hop number as an integer number for the multipath model when the path-loss exponent α=4,
(19)hopoptimal=d·(3·εmp2·Eelec)α.
Finally, the objective function for minimizing the energy for the partitioning path is written as
(20)MinEsisi+1=p{∑i=1n[2·Eelec+εmp(di)α]}xjalinkjsisi+1,subjectto(21)Constraint(1)hopoptimal=d·(3·εmp2·Eelec)α·∑j=1xj≤di,Constraint(2)xj={0,1},∀l∈E.
The first constraint guarantees that we obtain the optimal number of hops between the selected paths. The second constraint defines a decision variable for the selection and partitioning. We solve the optimization problem obtained by dualizing constraint (1) with the objective function using LR. We define a critical parameter to control the adaptive switching of the hop-by-hop QoS-routing protocol. Thus, we use the embedded criteria for each objective function that is related to the decision constraint to decide which path from the source to the sink to select. Consequently, the indicator is defined to indicate that the partitioned link lies on the selected optimal path; the indicator set value is 1 if the link lies on the selected path and is 0 otherwise:
(22)MinEsisi+1(μ)=p{∑i=1n[2·Eelec+εmp(di)4]}-μ(d·(3·εmp2·Eelec)α·∑j=1xj-di),Subjectto(23)Constraint(1)xj={0,1},∀l∈E,
where μ is defined as a vector of LR for all j where j=1,2,3,…,m.Table 1
The definition of all of the ratio parameters [31].
Parameter
Definition
Unit
E
elec
Energy dissipation rate to run the radio
50 nJ/bit
ε
fs
One-path model for the transmitter amplifier
10 pJ/bitm2
ε
mp
Multipath model for the transmitter amplifier
0.0013 pJ/bitm4
p
Data length
2000 bits


#### 3.3.2. Energy Efficiency Metric

The activity ratio is used as one of two parameters that minimize the energy consumption in WSNs during communication events. Other models that consider saving energy by scheduling sleep/awake cycles for transmission power control are related to MAC-layer behavior, such as windows contentions. In this paper, we do not address our problem in the MAC layer because our mathematical model is applied to using a routing metric to evaluate the energy of the sensor nodes.Figure5 defines the topology for our mathematical model. Figure 6(a) depicts a number of sensor nodes that are distributed randomly; an arrow shows the direction from the source to the sink. Figure 6(b) depicts a magnified intermediate portion of the path; it appears that some sensor nodes are not aligned along the selected path. Thus, we suggest using the concept of integer optimization programming to partition the sensor nodes that are not aligned along the path. Partitioning is performed using the projection of the positions of sensors onto the arrow, to determine how close the packet is to the sink. All of the sensor nodes know the location and the link quality of their neighbors and are distributed in a random form, as in Figure 6(a). Energy efficiency is defined as the number of packets that are delivered from the source to the sink with an optimal spanning over the lifetime of the sensor node. Thus, the energy efficiency is given by
(24)Eeff=PacketRec·RatioEnergy.Derivation of the mathematical partitioning model-chain topology. (a) Depiction of the type of distribution of the sensor nodes in the network domain. (b) Magnification of some aligned and nonaligned sensor nodes along the path inside the partition covered area of each path from the source to the sink.
(a)
(b)Thus,(25)Eeff=PRR(p)p{∑i=1n[2·Eelec+εmp(di)4]}xjalinkjsisi+1.PRR(p) is defined as the average packet reception ratio for packets that are transmitted from the source node to the sink sensor node when the traffic is generated in a random distributed manner, as shown in Figure 6(a).


#### 3.3.3. Delay Modeling

The delay and the throughput are two main fundamental performance metrics that have been studied intensely in WSN applications, but relatively little research has been devoted to multi-hop communication with uniform distributions. Performance-critical real-time WSN applications specify the acceptable requirements for minimum end-to-end delays and maximum packet delivery ratios. The proposed routing algorithm involves multi-hops, which increases the delay. Therefore, the proposed modeling assumes a link-quality distributed metric on each route between two sensor nodes in terms of the optimal hop number, which could have different delay guarantees, which are denoted asd(si,si+1). First, determine the optimal hops number that minimizes the delay as a function of the successful transmission of a packet, and then, jointly optimize the hops and estimation link quality to derive a scaling for law for minimizing the delay, as illustrated in Figure 15.The problem of determining the QoS route that satisfies the delay constraint is a difficult, nondeterministic polynomial-time problem and requires more information regarding nodes on their routes to the sink, which is always impossible to obtain in WSNs [32]. Hence, to solve the optimization problem, all of the source nodes and the intermediate nodes periodically calculate the estimated link quality from the one-hop neighborhood of each node, because the one-hop link quality is much easier to acquire. Suppose that the one requirement can be satisfied at each hop. Then, the end-to-end QoS requirement can also be met. More precisely, a node can satisfy the hop requirement by selecting the next hop according to the steady state of the estimated link quality. Therefore, the additive delay form of the delay allows the bounded delay to be evenly divided at each hop, which is described as follows.The end-to-end delay between any two sensor nodesss and sd over the set of paths P is given by Dsourcesdestination(P)=min{∑sid(si,si+1)}, where Dsourcesdestination is the minimum achievable delay when generated data are routed along the set of paths between so and sd. The delay d(si,si+1) between two nodes is the time that is required for successfully transmitting a packet after the node receives it. This time might include queuing time, contention time, transmission time, retransmission time, and propagation time.This approach is not similar to nonlinear programming, in which solving the problem depends on the end-to-end information that is acquired from the source node only. The approximate problem is solved by integer programming by partitioning the source and intermediate nodes, to collect the information at each hop to meet the overall QoS requirements under satisfied constraints. Therefore, the problem is formulated as an integer programming problem, and an excellent solution to this problem is provided by the LR method to uniformly partition the QoS requirements at all of the down-stream optimal hops, which is formulated as follows.Primary integer programming problem is(26)Dsourcesdestination=Min∑s∈P∑j=1xjd(si,si+1)alinkjsisi+1,subjecttoConstraint(1)∑j=1d(si,si+1)≤xj∇delay,
where ∇delay denotes the bounded delay, which depends on two factors: the number of hops taken and the delay of a node, which are of additive form and are denoted as hopsi and delays, respectively. Therefore,
(27)∇delay=delay0s+delayhops1s+1+delayhops2s+2+⋯+delayhopssinkd.
Thus, we rewrite ∇delay as
(28)∇delay=∑i=1ndelays+(n-1)·hopsi.
This form is designated as the additive form for ∇delay. The partitioning QoS requirements are met at all of the down-stream optimal hops. Lsdelay is the hop delay requirement along the path from the source to the sink, which is composed of hopsi  and which depends on the partition requirements at sensor node si. The hop delay requirement is equal to
(29)Lsdelay=∇delay-delayshopsi.
Then, we rewrite the first constraint (1):
(30)∑j=1d(si,si+1)≤xj·Lsdelay,
which means that the constraint expresses the delay of the selected route by the binary decision that xj=1if the delay is lower than the local delay requirement; otherwise, xj=0:
(31)Constraint(2)∑sdxj=1,Constraint(3)xj={0,1}.
There are two natural LR methods. The first method is obtained by dualizing constraint (1),
(32)ZDsourcesdestination(μ)=Min∑s∈P∑j=1xjd(si,si+1)+μ·(∑sdxj-1),subjecttoConstraint(1)∑j=1xjd(si,si+1)≤Lsdelay,Constraint(3)xij={0,1},∀l∈E.
The second method is obtained by dualizing constraint (1),
(33)ZDsourcesdestination(μ)=Min∑s∈P∑j=1xjd(si,si+1)+μ·(∑j=1xjd(si,si+1)-Lsdelay),Subjectto(34)Constraint(2)∑jxj=1,Constraint(3)xi,j={0,1},∀l∈E.
The proposed model assumes that each sensor node employs a carrier sense multiple access with a collision avoidance (CSMA/CA) technique to access the channel through a request to send/clear, to send/data/acknowledgment RTS/CTS/DATA/ACK handshaking to guarantee successful end-to-end or retransmission multi-hop transmission, which does not impose additional control overhead. For example, if sensor node i is to transmit to sensor node j, then sensor node i sends a transmission request to sensor node j and waits until sensor node i receives a message that indicates both that sensor j is ready to receive and that the sensing channel is idle.


## 3.1. The Problem Formulation

The problem of energy efficiency for object tracking in WSNs can be modeled with a directed network topologyG=(V,E), as shown in Figure 2, which is composed of sensor nodes that are distributed according to a two-dimensional Poisson distribution with respect to the density, where |V|=n is the number of sensor nodes and |E|=l denotes the set of links in the network. Each node is characterized by a transmission range. Moreover, each sensor node enters a sleep state once there is no ongoing transmission; otherwise, it enters a wakeup state. The existing link between two sensor nodes is defined as  e=(si,si+1) from node si to node si+1, where i=1,…,n.  Each link e∈E is characterized by two integer values: the energy consumption and the delay. A decision variable xj is defined as a variable that has the value 1 if there is connectivity between two sensor nodes, and 0 otherwise.


## 3.2. Wireless Channel Modeling

Unlike in wired networks, sensor nodes in wireless networks send information to each other by sharing common media. The key is how to organize the sensor nodes in the network topology to obtain as much as possible real-time information, such as video transmission over multi-hop communication scenarios as in event detection.  In general, there are two models for these common scenarios: (1) a channel-modeling-based point of view, in which the communication topology is a single communication channel model, and the key is to enable multiple signals to occupy the model, and (2) a packet-reception-based point of view for the mechanism to access the media where any simultaneous transmission will cause collisions. The channel-modeling-based perspective considers an approach that almost uses wireless mobile communication, while the packet-reception-based point of view has been investigated in computer networks, as in wireless random access networks [23].Designing real-time routing protocols for WSNs involves both approaches. The link quality is applied in wireless communication and considers the following factors in improving the PRR: the energy consumption, QoS parameters, and energy efficiency. The received signal envelope can be in several different modularities, for example, it can be modeled as Rayleigh fading. Given the modulation and coding schemes, the channel fading characteristic results in different PRR values because of radio wave reflection, refraction, and scattering, which give rise to the phenomenon known as wireless channels with multipath fading [24]. In this approach, the transmission channel exhibits the common characteristics of a time-varying channel; the statistical parameters that define the transmission channel vary slowly with respect to the interval of successful data packet transmission, which leads to complex performance analysis for the upper-layer protocols [25].Consequently, the alternative solution is to approximate and model the transmission medium fading channel as a discrete memoryless finite-state two-state Markov chain that is widely acknowledged as a reasonably accurate and mathematically tractable approach, which was first employed in [26], as shown in Figure 3, and is characterized by a specific EPR. This two-state modeling is proposed as a probabilistic process by using a Bernoulli distribution for distributing consecutive packets and the signal-bit-error correction mechanism into a finite number of level-crossing rates for SNR, denoted as Γto derive a mathematical model for the link quality, which is called a good channel and a bad channel, denoted as 0 and 1, respectively. Consider mapping a finite number of level-crossing rates as the tth state, in which an SNR that falls between Γgt and Γgt+1 represents a good state g. The bad channel state b represents a link quality of the channel propagation situation in which achieving a proper reception of the data packets is extremely difficult. Each state is associated with transition probabilities Pgb, where g,b∈{0,1} and ∑Pgb=1 toggle from state g to state b, which is dependent on the characteristic of the propagation environment, the transmission modulation scheme, and the detection technique, implemented at the receiver in which the SNR falls. In other words, the channel transition probability matrix is
(2)channeltransition=[p00p01p10p11]=[p1-p1-EPREPR].Figure 3
Two-state Markov chain transmission channel model.For a Rayleigh fading channel with additive white Gaussian noise, the received instantaneous SNRΥ is exponentially distributed as
(3)p(Υ)=1Υ0exp(-ΥΥ0),
where Υ0 is the mean of the received SNR.The steady-state probability of good channel stategt is given by
(4)π0=∫ΓgtΓgt+1p(Υ)dΥ=exp(-ΓgΥ0)-exp(-ΓgΥ0).This mathematical model is used to derive the relationship between PRR and SNR and evaluates the trade-offs between them. For example, when the SNR value is greater than 20~50 dB, PRR is almost 100%. A higher transmission power results in a higher signal to interference and SNR along the selected path but decreases the energy efficiency of the sensor node. Therefore, we determine the appropriate transmission power to reach the level-crossing rate of SNR at an appropriate value for a desired PRR value using a mathematical model that computes the optimal number of hopsn for the source to the sink. To derive the transition probabilities for consecutive packets p that are assumed to be probabilistic process, assume Pi to be a random variable that is equal to 1 if the ith packet is successfully received and 0 otherwise; then, let the Pi be independent and identically distributed for i=1,…,p. The expected value of Pi, E(Pi) is equal to the probability that packet i is successfully received, that is, Ps(i), so the average number of correctly received packets in the p transmission is
(5)PRR=1p∑i=1pPi,
where i=1,2,3⋯p.Thus, for real-time applications in WSNs in whichp is large, PRR can be closely approximated by the probability of a correctly received packet E(Pi)  [27–29]. For a quality link, suppose that each sensor node knows the link quality of its neighboring nodes through pe, which is represented as EPR [17]. All of the EPR calculations depend fundamentally on the SNR at the receiver. Therefore, the receiver must estimate the noise power and the power received because of the path-loss propagation. With this knowledge about the modulation scheme, the transmitted power, the path-loss propagation, and the noise floor, the receiver power and noise power for the EPR can be estimated. Thus, the PRR can be closely approximated for multi-hop communication by
(6)PRR≅E(Pi)=(1-pe)hop.
Some companies supply the EPR value for developers. For example, the Zigbee implementation on the MC13213 chip produced by the FreeScale Semiconductor Company [30] has a basic function of MLMELinkQuality that developers can use to obtain the current EPR. The link quality of a hop from the source to the sink is represented by EPR; thus, the value of the transmission of packets on each hop from the source to the final sink can be defined as an independent event that circumvents the complexities of retransmission. Furthermore, there is no coding. Thus, the single-bit-error rate leads to a packet error. The successful delivery probability for one packet for each hop is [15]
(7)PRR=(1-pe)hop,
where
(8)pe=1π0∫ΓgtΓgt+1(1-12exp-(p(Υ)/2)*(1/0.64))ρ8fdΥ.
For each correctly received packet, f data frame bits are received over a time period of
(9)fbitrate,
where bitrate = number  of  bits  per  symbol · symbolrate.Furthermore,(10)SNR=Pt-PL(d)-Sr,
where Pt is the transmitted power in dB and Sr is the sensitivity of the receiver in dBm. Finally, PL(d) is represented as
(11)PL(d)=PL(d0)+10γlog(dd0)+Xα,
where d is the total distance between the source and sink, d0 defines a distance reference between the two nodes, γ is the path loss exponent (which depends on the specific propagation environment), and Xα is a random variable drawn from a Gaussian distribution with a zero mean and a standard deviation of α units of dB, and ρ as the encoding ratio. The initial tests on the performance show the optimization of minimizing the energy consumption and the end-to-end delay pressure exerted by increasing the probability of the link estimation.


## 3.3. Multiconstrained QoS Multipath Routing in WSNs

Energy efficiency is considered to be the most important issue upon which the performance of the routing algorithm for WSNs depends. Apparently, the single-path multipath routing algorithm consumes lower energy than the multi-hop multipath because the energy that is required to transmit a packet over multiple paths is approximately twice as great as the energy required to transmit the same packet over a single path. Nevertheless, the multipath strategy could be used as a solution in most optimization routing methods in real-time WSN applications when it is desirable to set up multiconstraints QoS parameters such as energy consumption, reliability, and delay because of increasing the reliability of the data packet delivery and decreasing the average of the data packet delivery along the multipath available from the source to destination. Therefore, energy consumption, average delay, throughput, reliability, and other parameters are defined as QoS competitive constraints by different standardization stack layers (physical, MAC, network, and transport) in WSNs. These QoS parameters meet a trade-off between the resource limitations and multipath routing strategy, to ensure that the QoS requirement is guaranteed in the sensor networks.QoS parameter performances for all of the section layers are not the same and influence other QoS parameter performances. Therefore, any performance degradations of one parameter can degrade the performance of other parameters. Thus, the relationship between the QoS parameters in different layers in a typical communication stack must be defined to specify the architecture in which the QoS requirements could be provided in sensor networks. Figure4 illustrates a simplified proposed QoS model framework for WSNs. The proposed model enables the physical layer to coordinate the behavior of the MAC and the network layer to find optimal multipaths from the source to sink subject to two or more QoS competitive constraints. The application layer might have end-to-end delay as a QoS requirement, which will be coordinated in the network layer and the MAC. The proposed model used a physical layer to determine the link quality to the MAC and a network for metric routing. The proposed metric routing is used as a reference for the scheduling in the MAC and to control the adaptive switching of hop-by-hop QoS routing protocols in the network layer. Additionally, the duty cycle of the sensor node (wakeup/idle/sleep/transmit/received) action at the MAC layer will coordinate the optimization performance of the multipath routing protocol.Figure 4
The proposed QoS model framework for WSNs.


### 3.3.1. Energy Optimization Modeling

In this section, we derive a new mathematical model to minimize the power consumption, and then, we determine the optimal number of hops that are derived. There are two categories of techniques for delivering the report on event detection to the base-station or sink: (i) the former model, with a direct transmission to the sink, that is, a single-hop transmission, and (ii) multi-hop transmission, with the event reported based on multi-hop relaying between the intermediate nodes and the sink.Figure5 shows the one-dimensional linear array of sensor nodes in networks that can be used to represent most real-time wireless sensor applications, such as traffic monitoring and congestion control. This one-dimensional linear array method helps us to study the energy consumption in various multi-hop scenarios and to analyze and optimize the radio link for a specified topology. The analyzed topology assumes that the space between the sensors can be represented as equidistant sensor nodes.Figure 5
Linear energy consumption modeling.The energy model for sensor nodes in wireless networks is defined by assuming that a sensor node uses its power to carry out three primary functions: acquisition, communication, and data processing. The communication function consumes more energy than the other two functions because it includes two suboperations: energy transmission and energy reception. In most wireless sensor applications, the most commonly used energy model is called the first-order radio model. According to this model, the radio consumes an amount of energyEtx, which is defined below, to transmit p bitsof information over a specified distance d; the energy is defined for two categories of the transmission model [31]. Definition of these radio transmission model is listed in Table 1:
(12)Etx(p,d)={p·Eelec+p·εfs·dαforonepathtransmission,p·Eelec+p·εmp·dαformultipathtransmission,
where the amount of energy to receive p bits of information is
(13)Erx(p)=p·Eelec.
The amount of energy that is required to forward p bits of information is
(14)Etx(p,p)={2p·Eelec+p·εfs·dαforonepathtransmission,2p·Eelec+p·εmp·dαformultipathtransmission.
To transmit p bits of information over n hops along the selected path, the total energy required is
(15)Energysisi+1=p{∑i=1n[2·Eelec+εmp(di)α]}.
If we denote the energy dissipation as Pdiss, then to minimize the energy consumption, we formulate the optimization problem as
(16)Pdiss≥p{Etx+Erx}.
For our optimization problem, we define the previous equation as the objective function that we use to minimize the energy consumption for the linear array. The two variables that must be defined are the number of hops and the intermediate distance between two sensor nodes along the selected path. Thus, we can rewrite the equation as
(17)MinEnergysisi+1=p{∑i=1n[2·Eelec+εmp(di)α]}xjaljsisi+1.
Then, we must define the corrected constraints, which we obtain from both the number of hops from the source to the final sink and the definition of the intermediate distance between two sensor nodes. Because our application involves realistic WSN environments, it is necessary to find the optimal number of hops and the corresponding intermediate distance. For a fixed intermediate distance,
(18)∑i=1hopdi=d.
We must minimize the value of Esisi+1 when r1=r2=⋯=rn=totaldistance/numberofhops. We can obtain the optimal theoretical hop number as an integer number for the multipath model when the path-loss exponent α=4,
(19)hopoptimal=d·(3·εmp2·Eelec)α.
Finally, the objective function for minimizing the energy for the partitioning path is written as
(20)MinEsisi+1=p{∑i=1n[2·Eelec+εmp(di)α]}xjalinkjsisi+1,subjectto(21)Constraint(1)hopoptimal=d·(3·εmp2·Eelec)α·∑j=1xj≤di,Constraint(2)xj={0,1},∀l∈E.
The first constraint guarantees that we obtain the optimal number of hops between the selected paths. The second constraint defines a decision variable for the selection and partitioning. We solve the optimization problem obtained by dualizing constraint (1) with the objective function using LR. We define a critical parameter to control the adaptive switching of the hop-by-hop QoS-routing protocol. Thus, we use the embedded criteria for each objective function that is related to the decision constraint to decide which path from the source to the sink to select. Consequently, the indicator is defined to indicate that the partitioned link lies on the selected optimal path; the indicator set value is 1 if the link lies on the selected path and is 0 otherwise:
(22)MinEsisi+1(μ)=p{∑i=1n[2·Eelec+εmp(di)4]}-μ(d·(3·εmp2·Eelec)α·∑j=1xj-di),Subjectto(23)Constraint(1)xj={0,1},∀l∈E,
where μ is defined as a vector of LR for all j where j=1,2,3,…,m.Table 1
The definition of all of the ratio parameters [31].
Parameter
Definition
Unit
E
elec
Energy dissipation rate to run the radio
50 nJ/bit
ε
fs
One-path model for the transmitter amplifier
10 pJ/bitm2
ε
mp
Multipath model for the transmitter amplifier
0.0013 pJ/bitm4
p
Data length
2000 bits


### 3.3.2. Energy Efficiency Metric

The activity ratio is used as one of two parameters that minimize the energy consumption in WSNs during communication events. Other models that consider saving energy by scheduling sleep/awake cycles for transmission power control are related to MAC-layer behavior, such as windows contentions. In this paper, we do not address our problem in the MAC layer because our mathematical model is applied to using a routing metric to evaluate the energy of the sensor nodes.Figure5 defines the topology for our mathematical model. Figure 6(a) depicts a number of sensor nodes that are distributed randomly; an arrow shows the direction from the source to the sink. Figure 6(b) depicts a magnified intermediate portion of the path; it appears that some sensor nodes are not aligned along the selected path. Thus, we suggest using the concept of integer optimization programming to partition the sensor nodes that are not aligned along the path. Partitioning is performed using the projection of the positions of sensors onto the arrow, to determine how close the packet is to the sink. All of the sensor nodes know the location and the link quality of their neighbors and are distributed in a random form, as in Figure 6(a). Energy efficiency is defined as the number of packets that are delivered from the source to the sink with an optimal spanning over the lifetime of the sensor node. Thus, the energy efficiency is given by
(24)Eeff=PacketRec·RatioEnergy.Derivation of the mathematical partitioning model-chain topology. (a) Depiction of the type of distribution of the sensor nodes in the network domain. (b) Magnification of some aligned and nonaligned sensor nodes along the path inside the partition covered area of each path from the source to the sink.
(a)
(b)Thus,(25)Eeff=PRR(p)p{∑i=1n[2·Eelec+εmp(di)4]}xjalinkjsisi+1.PRR(p) is defined as the average packet reception ratio for packets that are transmitted from the source node to the sink sensor node when the traffic is generated in a random distributed manner, as shown in Figure 6(a).


### 3.3.3. Delay Modeling

The delay and the throughput are two main fundamental performance metrics that have been studied intensely in WSN applications, but relatively little research has been devoted to multi-hop communication with uniform distributions. Performance-critical real-time WSN applications specify the acceptable requirements for minimum end-to-end delays and maximum packet delivery ratios. The proposed routing algorithm involves multi-hops, which increases the delay. Therefore, the proposed modeling assumes a link-quality distributed metric on each route between two sensor nodes in terms of the optimal hop number, which could have different delay guarantees, which are denoted asd(si,si+1). First, determine the optimal hops number that minimizes the delay as a function of the successful transmission of a packet, and then, jointly optimize the hops and estimation link quality to derive a scaling for law for minimizing the delay, as illustrated in Figure 15.The problem of determining the QoS route that satisfies the delay constraint is a difficult, nondeterministic polynomial-time problem and requires more information regarding nodes on their routes to the sink, which is always impossible to obtain in WSNs [32]. Hence, to solve the optimization problem, all of the source nodes and the intermediate nodes periodically calculate the estimated link quality from the one-hop neighborhood of each node, because the one-hop link quality is much easier to acquire. Suppose that the one requirement can be satisfied at each hop. Then, the end-to-end QoS requirement can also be met. More precisely, a node can satisfy the hop requirement by selecting the next hop according to the steady state of the estimated link quality. Therefore, the additive delay form of the delay allows the bounded delay to be evenly divided at each hop, which is described as follows.The end-to-end delay between any two sensor nodesss and sd over the set of paths P is given by Dsourcesdestination(P)=min{∑sid(si,si+1)}, where Dsourcesdestination is the minimum achievable delay when generated data are routed along the set of paths between so and sd. The delay d(si,si+1) between two nodes is the time that is required for successfully transmitting a packet after the node receives it. This time might include queuing time, contention time, transmission time, retransmission time, and propagation time.This approach is not similar to nonlinear programming, in which solving the problem depends on the end-to-end information that is acquired from the source node only. The approximate problem is solved by integer programming by partitioning the source and intermediate nodes, to collect the information at each hop to meet the overall QoS requirements under satisfied constraints. Therefore, the problem is formulated as an integer programming problem, and an excellent solution to this problem is provided by the LR method to uniformly partition the QoS requirements at all of the down-stream optimal hops, which is formulated as follows.Primary integer programming problem is(26)Dsourcesdestination=Min∑s∈P∑j=1xjd(si,si+1)alinkjsisi+1,subjecttoConstraint(1)∑j=1d(si,si+1)≤xj∇delay,
where ∇delay denotes the bounded delay, which depends on two factors: the number of hops taken and the delay of a node, which are of additive form and are denoted as hopsi and delays, respectively. Therefore,
(27)∇delay=delay0s+delayhops1s+1+delayhops2s+2+⋯+delayhopssinkd.
Thus, we rewrite ∇delay as
(28)∇delay=∑i=1ndelays+(n-1)·hopsi.
This form is designated as the additive form for ∇delay. The partitioning QoS requirements are met at all of the down-stream optimal hops. Lsdelay is the hop delay requirement along the path from the source to the sink, which is composed of hopsi  and which depends on the partition requirements at sensor node si. The hop delay requirement is equal to
(29)Lsdelay=∇delay-delayshopsi.
Then, we rewrite the first constraint (1):
(30)∑j=1d(si,si+1)≤xj·Lsdelay,
which means that the constraint expresses the delay of the selected route by the binary decision that xj=1if the delay is lower than the local delay requirement; otherwise, xj=0:
(31)Constraint(2)∑sdxj=1,Constraint(3)xj={0,1}.
There are two natural LR methods. The first method is obtained by dualizing constraint (1),
(32)ZDsourcesdestination(μ)=Min∑s∈P∑j=1xjd(si,si+1)+μ·(∑sdxj-1),subjecttoConstraint(1)∑j=1xjd(si,si+1)≤Lsdelay,Constraint(3)xij={0,1},∀l∈E.
The second method is obtained by dualizing constraint (1),
(33)ZDsourcesdestination(μ)=Min∑s∈P∑j=1xjd(si,si+1)+μ·(∑j=1xjd(si,si+1)-Lsdelay),Subjectto(34)Constraint(2)∑jxj=1,Constraint(3)xi,j={0,1},∀l∈E.
The proposed model assumes that each sensor node employs a carrier sense multiple access with a collision avoidance (CSMA/CA) technique to access the channel through a request to send/clear, to send/data/acknowledgment RTS/CTS/DATA/ACK handshaking to guarantee successful end-to-end or retransmission multi-hop transmission, which does not impose additional control overhead. For example, if sensor node i is to transmit to sensor node j, then sensor node i sends a transmission request to sensor node j and waits until sensor node i receives a message that indicates both that sensor j is ready to receive and that the sensing channel is idle.


## 3.3.1. Energy Optimization Modeling

In this section, we derive a new mathematical model to minimize the power consumption, and then, we determine the optimal number of hops that are derived. There are two categories of techniques for delivering the report on event detection to the base-station or sink: (i) the former model, with a direct transmission to the sink, that is, a single-hop transmission, and (ii) multi-hop transmission, with the event reported based on multi-hop relaying between the intermediate nodes and the sink.Figure5 shows the one-dimensional linear array of sensor nodes in networks that can be used to represent most real-time wireless sensor applications, such as traffic monitoring and congestion control. This one-dimensional linear array method helps us to study the energy consumption in various multi-hop scenarios and to analyze and optimize the radio link for a specified topology. The analyzed topology assumes that the space between the sensors can be represented as equidistant sensor nodes.Figure 5
Linear energy consumption modeling.The energy model for sensor nodes in wireless networks is defined by assuming that a sensor node uses its power to carry out three primary functions: acquisition, communication, and data processing. The communication function consumes more energy than the other two functions because it includes two suboperations: energy transmission and energy reception. In most wireless sensor applications, the most commonly used energy model is called the first-order radio model. According to this model, the radio consumes an amount of energyEtx, which is defined below, to transmit p bitsof information over a specified distance d; the energy is defined for two categories of the transmission model [31]. Definition of these radio transmission model is listed in Table 1:
(12)Etx(p,d)={p·Eelec+p·εfs·dαforonepathtransmission,p·Eelec+p·εmp·dαformultipathtransmission,
where the amount of energy to receive p bits of information is
(13)Erx(p)=p·Eelec.
The amount of energy that is required to forward p bits of information is
(14)Etx(p,p)={2p·Eelec+p·εfs·dαforonepathtransmission,2p·Eelec+p·εmp·dαformultipathtransmission.
To transmit p bits of information over n hops along the selected path, the total energy required is
(15)Energysisi+1=p{∑i=1n[2·Eelec+εmp(di)α]}.
If we denote the energy dissipation as Pdiss, then to minimize the energy consumption, we formulate the optimization problem as
(16)Pdiss≥p{Etx+Erx}.
For our optimization problem, we define the previous equation as the objective function that we use to minimize the energy consumption for the linear array. The two variables that must be defined are the number of hops and the intermediate distance between two sensor nodes along the selected path. Thus, we can rewrite the equation as
(17)MinEnergysisi+1=p{∑i=1n[2·Eelec+εmp(di)α]}xjaljsisi+1.
Then, we must define the corrected constraints, which we obtain from both the number of hops from the source to the final sink and the definition of the intermediate distance between two sensor nodes. Because our application involves realistic WSN environments, it is necessary to find the optimal number of hops and the corresponding intermediate distance. For a fixed intermediate distance,
(18)∑i=1hopdi=d.
We must minimize the value of Esisi+1 when r1=r2=⋯=rn=totaldistance/numberofhops. We can obtain the optimal theoretical hop number as an integer number for the multipath model when the path-loss exponent α=4,
(19)hopoptimal=d·(3·εmp2·Eelec)α.
Finally, the objective function for minimizing the energy for the partitioning path is written as
(20)MinEsisi+1=p{∑i=1n[2·Eelec+εmp(di)α]}xjalinkjsisi+1,subjectto(21)Constraint(1)hopoptimal=d·(3·εmp2·Eelec)α·∑j=1xj≤di,Constraint(2)xj={0,1},∀l∈E.
The first constraint guarantees that we obtain the optimal number of hops between the selected paths. The second constraint defines a decision variable for the selection and partitioning. We solve the optimization problem obtained by dualizing constraint (1) with the objective function using LR. We define a critical parameter to control the adaptive switching of the hop-by-hop QoS-routing protocol. Thus, we use the embedded criteria for each objective function that is related to the decision constraint to decide which path from the source to the sink to select. Consequently, the indicator is defined to indicate that the partitioned link lies on the selected optimal path; the indicator set value is 1 if the link lies on the selected path and is 0 otherwise:
(22)MinEsisi+1(μ)=p{∑i=1n[2·Eelec+εmp(di)4]}-μ(d·(3·εmp2·Eelec)α·∑j=1xj-di),Subjectto(23)Constraint(1)xj={0,1},∀l∈E,
where μ is defined as a vector of LR for all j where j=1,2,3,…,m.Table 1
The definition of all of the ratio parameters [31].
Parameter
Definition
Unit
E
elec
Energy dissipation rate to run the radio
50 nJ/bit
ε
fs
One-path model for the transmitter amplifier
10 pJ/bitm2
ε
mp
Multipath model for the transmitter amplifier
0.0013 pJ/bitm4
p
Data length
2000 bits


## 3.3.2. Energy Efficiency Metric

The activity ratio is used as one of two parameters that minimize the energy consumption in WSNs during communication events. Other models that consider saving energy by scheduling sleep/awake cycles for transmission power control are related to MAC-layer behavior, such as windows contentions. In this paper, we do not address our problem in the MAC layer because our mathematical model is applied to using a routing metric to evaluate the energy of the sensor nodes.Figure5 defines the topology for our mathematical model. Figure 6(a) depicts a number of sensor nodes that are distributed randomly; an arrow shows the direction from the source to the sink. Figure 6(b) depicts a magnified intermediate portion of the path; it appears that some sensor nodes are not aligned along the selected path. Thus, we suggest using the concept of integer optimization programming to partition the sensor nodes that are not aligned along the path. Partitioning is performed using the projection of the positions of sensors onto the arrow, to determine how close the packet is to the sink. All of the sensor nodes know the location and the link quality of their neighbors and are distributed in a random form, as in Figure 6(a). Energy efficiency is defined as the number of packets that are delivered from the source to the sink with an optimal spanning over the lifetime of the sensor node. Thus, the energy efficiency is given by
(24)Eeff=PacketRec·RatioEnergy.Derivation of the mathematical partitioning model-chain topology. (a) Depiction of the type of distribution of the sensor nodes in the network domain. (b) Magnification of some aligned and nonaligned sensor nodes along the path inside the partition covered area of each path from the source to the sink.
(a)
(b)Thus,(25)Eeff=PRR(p)p{∑i=1n[2·Eelec+εmp(di)4]}xjalinkjsisi+1.PRR(p) is defined as the average packet reception ratio for packets that are transmitted from the source node to the sink sensor node when the traffic is generated in a random distributed manner, as shown in Figure 6(a).


## 3.3.3. Delay Modeling

The delay and the throughput are two main fundamental performance metrics that have been studied intensely in WSN applications, but relatively little research has been devoted to multi-hop communication with uniform distributions. Performance-critical real-time WSN applications specify the acceptable requirements for minimum end-to-end delays and maximum packet delivery ratios. The proposed routing algorithm involves multi-hops, which increases the delay. Therefore, the proposed modeling assumes a link-quality distributed metric on each route between two sensor nodes in terms of the optimal hop number, which could have different delay guarantees, which are denoted asd(si,si+1). First, determine the optimal hops number that minimizes the delay as a function of the successful transmission of a packet, and then, jointly optimize the hops and estimation link quality to derive a scaling for law for minimizing the delay, as illustrated in Figure 15.The problem of determining the QoS route that satisfies the delay constraint is a difficult, nondeterministic polynomial-time problem and requires more information regarding nodes on their routes to the sink, which is always impossible to obtain in WSNs [32]. Hence, to solve the optimization problem, all of the source nodes and the intermediate nodes periodically calculate the estimated link quality from the one-hop neighborhood of each node, because the one-hop link quality is much easier to acquire. Suppose that the one requirement can be satisfied at each hop. Then, the end-to-end QoS requirement can also be met. More precisely, a node can satisfy the hop requirement by selecting the next hop according to the steady state of the estimated link quality. Therefore, the additive delay form of the delay allows the bounded delay to be evenly divided at each hop, which is described as follows.The end-to-end delay between any two sensor nodesss and sd over the set of paths P is given by Dsourcesdestination(P)=min{∑sid(si,si+1)}, where Dsourcesdestination is the minimum achievable delay when generated data are routed along the set of paths between so and sd. The delay d(si,si+1) between two nodes is the time that is required for successfully transmitting a packet after the node receives it. This time might include queuing time, contention time, transmission time, retransmission time, and propagation time.This approach is not similar to nonlinear programming, in which solving the problem depends on the end-to-end information that is acquired from the source node only. The approximate problem is solved by integer programming by partitioning the source and intermediate nodes, to collect the information at each hop to meet the overall QoS requirements under satisfied constraints. Therefore, the problem is formulated as an integer programming problem, and an excellent solution to this problem is provided by the LR method to uniformly partition the QoS requirements at all of the down-stream optimal hops, which is formulated as follows.Primary integer programming problem is(26)Dsourcesdestination=Min∑s∈P∑j=1xjd(si,si+1)alinkjsisi+1,subjecttoConstraint(1)∑j=1d(si,si+1)≤xj∇delay,
where ∇delay denotes the bounded delay, which depends on two factors: the number of hops taken and the delay of a node, which are of additive form and are denoted as hopsi and delays, respectively. Therefore,
(27)∇delay=delay0s+delayhops1s+1+delayhops2s+2+⋯+delayhopssinkd.
Thus, we rewrite ∇delay as
(28)∇delay=∑i=1ndelays+(n-1)·hopsi.
This form is designated as the additive form for ∇delay. The partitioning QoS requirements are met at all of the down-stream optimal hops. Lsdelay is the hop delay requirement along the path from the source to the sink, which is composed of hopsi  and which depends on the partition requirements at sensor node si. The hop delay requirement is equal to
(29)Lsdelay=∇delay-delayshopsi.
Then, we rewrite the first constraint (1):
(30)∑j=1d(si,si+1)≤xj·Lsdelay,
which means that the constraint expresses the delay of the selected route by the binary decision that xj=1if the delay is lower than the local delay requirement; otherwise, xj=0:
(31)Constraint(2)∑sdxj=1,Constraint(3)xj={0,1}.
There are two natural LR methods. The first method is obtained by dualizing constraint (1),
(32)ZDsourcesdestination(μ)=Min∑s∈P∑j=1xjd(si,si+1)+μ·(∑sdxj-1),subjecttoConstraint(1)∑j=1xjd(si,si+1)≤Lsdelay,Constraint(3)xij={0,1},∀l∈E.
The second method is obtained by dualizing constraint (1),
(33)ZDsourcesdestination(μ)=Min∑s∈P∑j=1xjd(si,si+1)+μ·(∑j=1xjd(si,si+1)-Lsdelay),Subjectto(34)Constraint(2)∑jxj=1,Constraint(3)xi,j={0,1},∀l∈E.
The proposed model assumes that each sensor node employs a carrier sense multiple access with a collision avoidance (CSMA/CA) technique to access the channel through a request to send/clear, to send/data/acknowledgment RTS/CTS/DATA/ACK handshaking to guarantee successful end-to-end or retransmission multi-hop transmission, which does not impose additional control overhead. For example, if sensor node i is to transmit to sensor node j, then sensor node i sends a transmission request to sensor node j and waits until sensor node i receives a message that indicates both that sensor j is ready to receive and that the sensing channel is idle.


## 4. Performance Evaluation

LR becomes a much more attractive method out of the very few solution methods in optimization that cut across the domains of integer programming because its procedure uses the idea of relaxing the explicit constraints by bringing them into the objective function with the associated Lagrange multiplierμ. With the help of LR, the proposed algorithm can choose the optimal μ for a given two-node pair, and the constrained optimal path problem can be solved with respect to the modified objective function of energy consumption equation (22) and the delay equation (34) or (33). LR permits the development of lower bound constraints for both energy consumption equations (21) and (23) and delay equations (30) and (31) parameters on the optimal length of a constrained optimal path. These lower bounds can be of considerable value when demonstrating that a specific path from the source to the sink is generated by solving the partitioning link quality subproblems.As we observed from Figure7, a key to finding the optimal number of hops for a multipath from the source to the sink can be exposed to the convex envelope or the convex hull of the objective function, by adding an objective cut. In fact, the evolution of power consumption and end-to-end delay for a path that adopts the objective functions for the power consumption and delay level cut at 5 hops corresponds to a feasible solution. Therefore, the value of the power consumption and the end-to-end delay functions are 0.033 mW and 1.6 sec, respectively, which define an upper bound. Moreover, by the weak duality, the dual value can be specified for the power consumption and end-to-end delay as 0.01 mW and 0.1 sec, respectively, which defines the lower bound. Therefore, adding an objective cut of 0.01≤f(x)≤0.033 for the power consumption and 0.1sec≤f(x)≤1.6sec for the end-to-end delay to the original problem will include the optimal solution.Figure 7
Adopting the objective function with the level cut method for the single-path routing algorithm.To illustrate the main concepts of the proposed mathematical modeling, we used the LINGO optimization module [33] to consider a linear wireless network with uniform topology that is composed of 50 nodes, as described in Figure 6, with N+1 nodes. The source sensor node and the sink are placed inside the wireless sensor area; each sensor node has a connectivity that is associated with two positive QoS constraints. We evaluated the object-tracking scenario by studying the behavior of cars passing along the highway in a one-dimensional sensor network topology, as shown in Figure 6. The evaluation of the proposed model has been compared, through experimentation, with the efficiency of other protocols, namely, ReInForM [16], MCMP [18], and ECMP [19], in terms of several performance parameters. These parameters include the power consumption, the average end-to-end delay, and the successfully received packet ratio. The success probability of the transmission channel is chosen from 0.1 to 0.8, which implies a good state for the link quality.The assumption builds on a scenario of cars that enter a highway under specified conditions. First, the total number of cars on the highway is very large. Second, a single car uses a certain percentage of the highway resources. Third, the decision of whether to enter the highway is made independently by each car driver. These conditions mean that the car arrival on the highway, with a certain rate, follows a Poisson arrival process. If any one of the three conditions is not met, then the Poisson arrival will fail to predict the arrival of a packet during the detection of the event. Usually, each sensor node is assumed to be aware of its geographic location, and the transmission range of the nodes is approximately 12.35 m because a few sensor nodes are assumed to be video sensors that have more constraints, such as a limitation in the sensing coverage area and the field of view (FoV). The model assumes that each sensor video node is represented in two dimensions, where the FoV is defined as a triangle denoted by a 4-tuple sensor (P,dis,V→,∝), P is the position of the video sensor node, dist is the depth of view for the camera, V→ represents the vector line sight of the camera FoV that determines the sensing direction, and ∝ is the angle of the FoV on both sides of V→. The dis varies according to the platform of the WSN, for example, on a Samsung Player Addict mobile phone for which the dis is approximately 2.6 m. The path-loss exponent α and the reference distance d0 are 4 and 1, respectively. The proposed model uses kinematic equations to identify the time period when the cars pass the sensing range at a certain speed. Therefore, the probability density function distribution for Poisson Arrival of seeing a number of cars in  a specified time period is given as Px(t)=((λt)x/x!)e-λt, where t is used to define the interval 0 to t, x is the total number of car arrivals in this interval, and λ is the total average arrival rate in arrivals/second. For example, consider a highway with an average of 1 car arriving every 10 seconds. Here, λ is equal to an arrival rate of approximately 0.1 car/second. A video sensor detects the car and delivers the location information of the car to intermediate sensor nodes and then to the sink, with the probability of transmission denoted as β. Starting with different seeds for the probability of arrival and the transmission λ and β, the multipath shown in Figure 8 can be generated.Figure 8
Adopting the objective function with the level cut method for the multipath routing algorithm.The transmission between the end nodes source and the sink can occur in a single hop, or up to multihop communication according to the remaining intermediate nodes. Proponents of multi-hop communication routing argue that more short hops are preferable to fewer long hops because of the estimation of the link quality with a finite number of observations of distributed channel access. Suppose that a node wakes up to monitor the highway atp random times which are uniformly distributed throughout the duty cycle. When the node wakes up, it recodes the average of the SNR at that time, which appears to be sufficient to obtain a very good estimate of the link inefficiency, even for bad links.We were interested in finding the average of the SNR values along the partitioning routes to optimize the energy efficiency of the network topology by minimizing the energy consumption and the delay. We sought to accomplish this goal because the SNR along the route is larger for multi-hop communication and accounts for the important practical issues of resource allocation, energy, and delay constraints. For example, let there be two links, with both of them affected by channel fading, and the measured SNR is 17 db  for one link and 25 db for the other. Thus, it could happen that when the channel fading is on and it affects both links in the same way, the SNR of the former link falls to 5 db whereas the latter still enjoys an SNR of 17 db, which is a more efficient link quality than the former.Therefore, to compare the two links, it is useful to account for their estimated SNR values, which are considered to be very helpful in refining the link quality judgment. One way to accomplish this goal is to weigh the calculated efficiency by the increasing function of SNR, that is, the derivative of (3) with respect to p(Υ). However, the determination of the increase in the SNR is based on the distance between the partition nodes, as shown in Figure 9, which shows scatter plots of measured PRR describing the physical interaction of the channel and the radio model conditioned on a finite number of level-crossing rates for the SNR. The expected PRR is then expected from this SNR and is given by pe. Figure 10 describes the measured PRR values versus the corresponding average SNR.Figure 9
The interaction of SNR with the channel to determine the transitional region.Figure 10
Analytical PRR with determining various regions of link quality.


### 4.1. The Influence of the Estimation Link Quality to the Energy Consumption

In the deployment of nodes and the use of a common media for transmission and reception, various multi-hop paths are generated from a single node to another node, as illustrated in Figure6(b). The amount of energy that is consumed in the transmission of data packets from a specific node to the sink or even to an intermediate node on the link has a strong relationship with obtaining a good steady state of the wireless channel between two partitioning nodes. Therefore, routing based on statistical parameters that define the transmission channel is more efficient than a routing algorithm that is based on a straight-forward hop count.Figure12 shows the influence of increasing the link quality on the energy consumption when solving the optimization problem using the constraints of the transmission range, the optimal number of hops, and the integer decision variable. It appears that direct transmission always consumes 10 times more energy than multi-hop communication does whenever the transmission range increases or decreases, because the distance between the source and sink is fixed, taking D=150 m, for example. In multi-hop communication, the amount of energy that is consumed by the optimal aligned partitioned route globally decreases whenever the probability of the link efficiency estimation increases. To understand this behavior, that is, the increase, consider that the probability of the wireless link estimation will control to reduce the packet error rate by improving the SNR, by decreasing the distance between two adjacent nodes. This construct leads to deploying or waking a new node in the network, which then increases the network density deployment. The increase in the link quality implicitly assumes that a new aligned node on the partitioning route has a relatively high duty cycle that can determine the recent state of a wireless channel to each node, to transmit or receive packets, while other unaligned nodes implicitly save energy consumption by turning their radio off. Each node obtains link quality information about its neighbors, which provides a basis for establishing the solution of minimizing the energy consumption. Figure 11 illustrates the energy-limited node network scenario of an event-reporting scheme that assumes that the distance between the occurring event and two sensor nodes N1 and N2 are equal to 5.21 unit distance (ud) and 3.21 ud, respectively, the distance between each two adjacent nodes being nearly 12.45 ud. In this case, if the event is reported by N2, then the number of hops from N2 to the sink is five. When the event is reported by N1, the number of hops is more than five because the increasing quality of the wireless channel provides conditional controlling of the wireless sensor node density; the number of hops required to report an event does not increase when new nodes are deployed. The results obtained when partitioning the aligned nodes are seen in Figure 6(b). The energy consumption decreases with the increasing estimation of the link quality when satisfing the constraints on the number of hops that are required to report the event, which does not exceed the intermediate transmission radius, as seen in Figure 12 (where the amount of energy decreases by the aversion-serrated shape).Figure 11
Event reporting scenario in WSNs with increasing deployment nodes.Figure 12
The average amount of energy required to report an event under integer optimization programming.Figure13 depicts the energy efficiency of the WSN when solving the optimization problem by optimizing both the energy consumption and the PRR. The figure shows that the lifetime of the wireless sensor node increases when the packet travels along a number of partition routes which are estimated with an efficient link quality that connects the sensor nodes in the network domain. This increasing lifetime demonstrates that each sensor node unaligned on the partition route will enter a sleep state once because there is no in/ongoing transmission; it will otherwise enter the wakeup state whenever it is aligned in the partitioned route.Figure 13
The maximization of the lifetime under integer optimization programming. (1) Upper-bounded lifetime. (2) Node-density control. (3) Partitioning link quality.Unlike the proposed algorithm, the node density control algorithm [7] defines the reporting of the lifetime as a noncumulative function that depends on the total number of events that are detected by a network comprising of N nodes given as
(35)lifetime=energyconsumptionaveragenumberofevents.This procedure means optimizing the lifetime because more nodes are deployed at the same time. We have given an example to discuss the results. Consider that there areN nodes deployed along a highway to monitor the traffic cars that are present in the camera FOV. The routing from the source to sink during a specified period of time is given by thelengthoftrajectory/thevelocityofcar, which is 4.10 s with an acceleration of 600 m/s. According to kinematic equations, the distance that would be displaced during this period of time is 50.4. Suppose that the number of deployed nodes is 10. Then, the hop distance is 5.04, and therefore the lifetime is nearly 0.54 s. Whenever the period of time increases, the lifetime will decrease because of the inefficiency of the regular deployment of nodes, which is performed to keep track of the events and to route the report of the occurring events. On the other hand, the proposed algorithm designs a more efficient regular partitioning topology by performing link measurements during the times when nodes are awake for transmission or reception of events, with very little extra energy spent.Unlike the upper bound algorithm [8], the proposed algorithm uses the partitioning optimization to define the bounds on the lifetime of the sensor networks by discovering the independence of the source behavior, the partitioning region, the normal-log path loss modeling, and the residual energy. The proposed model achieves more energy efficiency than the two existing algorithms, namely, the node density control for maximizing the lifetime and the upper-bounded lifetime algorithms, which perform at approximately 67.91% and 96.91%, respectively.Figure14 shows the total power consumption in the network with four models that perform multipath routing algorithm equally. As expected, the proposed model performed better compared to ECMP and MCMP, which results from the fact that both the ECMP and MCMP models are deterministic zero-one problems in which all of the objective functions and constraints are linear. Moreover, the number of constraints actually presents as 2|N[ι]|+2, where |N[ι]| defines the number of sensor nodes in the networks. Therefore, the size of the search space will increase proportionately to the increase in the node density. Thus, it is obvious that whenever the number of nodes increases, finding the optimal multipath becomes too large for acceptable computation time. The search method for finding multipaths from the source to the sink that support QoS requirements is solved by the Balas algorithm, which is based on a random selection for the node at each next hop until the sink is selected. Consequently, the ECMP model can achieve more power savings, which are approximately 43.41% compared to the MCMP model because the MCMP has used 15.45% more multipath routing than ECMP. These results mean that the ECMO algorithm supports QoS requirements in sensor networks based on well-defined QoS constraints to avoid any exhaustion of energy that occurs when delivering the packets along the selected multipath.Figure 14
The power consumption comparison.Figure 15
The minimization end-to-end delay under integer optimization programming.Unlike both models, the proposed model routes the information over the optimal number of hops from the source to the sink. The strength of the proposed model lies on the fact that it accomplishes a trade-off between the optimal number of hops and the minimum energy consumption by selecting a path with the optimal number of hops. The proposed model depends on a new technical search method for selecting multipath routing based on Lagrange multipliersμ for given two nodes with an optimal number of hops. Then, it makes a transformation of the constrained optimal path problem to the objective function of the energy consumption equation (22), using the level cut off method. Therefore, this transformation for the power consumption will include the optimal solution, as depicted in Figure 8, which caused the proposed model to achieve more power savings (approximately 74.42% compared to the MCMP and ECMP models).The power consumption for ReInForM for each successful packet received is given byNs∑i=0k-1(1-pe)i=(1-(1-pe)klog(1-r))/elog(1-(1-pe)k), where k is the number of hops, and Ns is defined as the number of transmission multipaths for each successfully received packet, which can be expressed as Ns=log(1-r)/log(1-(1-pe)k), where r defines the reliability of the transmission channel rate. Therefore, the ReInForM protocol consumes more power than the other models because when there is increase in 1-pe, the ReInForM protocol will demand more multipaths to transmit the packet with desirable reliability.


### 4.2. The Influence of Estimation Link Quality on the Delay

To address the delay constrained environment, a comparison is made between the single hop and the multi-hop methods presented under delay constraints for the delivery delay, which is well approximated by the proposed model (which represents the behaviour of each node). Figure15 indicates that the benefits of multi-hop communication are eroded by the delay under delay-constraint. The figure shows the expected average data delivery delay from the source to the sink versus the probability of the estimation of the link quality. The graph of the delay is a concave function. Although a good steady state of the transmission varies, the delay is almost of the same pattern, and therefore a good steady state satisfies the constraints, and the minimum delay is a global optimization value.The figure demonstrates that the delay decreases when the packet travels along links with estimated efficiency that connects the sensor nodes in the network domain. Because of the increasing probability that a link will increase the sensor node deployment, this relation results in minimizing the delay by applying the integer optimization problem constraint in which the end-to-end delay is constrained to find the optimal aligned partitioned route.In addition, for a comparison in terms of the average end-to-end delay, both the ECMP and MCMP models perform equally with little difference. Because the multipaths selected by the two models are different in terms of the number of hops, as illustrated in Figure16, it appears that the ECMP model uses a smaller group of longer multipaths than the MCMP model. Therefore, the MCMP model tends to consume more power than the ECMP, which lowers the average end-to-end delay. The similarity of the performances of the ECMP and MCMP justifies that the trade-off between the power consumption and the average end-to-end delay is impacted by the number of selected multipaths, which reveals that the ECMP model uses a smaller or longer multipath resulting in lower power consumption with a higher average end-to-end delay.Figure 16
The average end-to-end delay comparison.In contrast, the proposed model outperforms the others models by using its preferred selected multipath with an optimal number of hops. This result reveals, in general, that the proposed model uses the multipath with the optimal number of hops compared to the other models. Therefore, the proposed model is more likely to lead to a lower average end-to-end delay.


### 4.3. The Influence of the Estimation Link Quality on the Packet Received Ratio

PRR is considered to be one of the most important metrics in real-time WSNs applications. This metric indicates the number of packets that meets the specified QoS requirements. The proposed model has extended the investigated network performance by studying the influence of the optimal hop number on the relationship between the SNR and the packet delivery ratio (i.e., the ratio of the received packets to the attempted packet transmission). Figure17 illustrates the relationship between PRR and SNR for the various numbers of hops for the integer optimization problem constraint in which the energy consumption is constrained. For the single hop, multihop, and optimal number of hops, the figure demonstrates that the optimal number of hops along a selected partition path achieves a good PRR. In the experiments, PRR was in the range of 51–90%. This result was the optimal rate for the optimal energy consumption at which there is a sufficiently strong signal reception strength, which had an SNR value in the range of 1–25 dB. The single hop of the selected partition path that consumed more energy had a PRR of 98.81%. Additionally, the multihop of a selected partition path PRR was in the range of 81–99%. All of the models perform equally in terms of the PRR for the reliability of transmission channels, as illustrated in Figure 18. To have a close view of the PRR, the curves of all of the models show the PRR on a log scale. As expected, the proposed model achieves the best performance of the PRR, which is approximately 96% compared to the other models, the ECMP, MCMP, and ReInForm, that achieved 94%, 92%, and 88%, respectively. Usually, the packets reception ratio increases logarithmically whenever the reliability of the transmission channel rate increases, because of ensuring more packets to deliver to the sink in a successful manner with a small expiring ratio for the packets lost.Figure 17
The relationship between the PRR and the SNR for single hop, multihop, and optimal hops.Figure 18
The packet success ratio comparison.


## 4.1. The Influence of the Estimation Link Quality to the Energy Consumption

In the deployment of nodes and the use of a common media for transmission and reception, various multi-hop paths are generated from a single node to another node, as illustrated in Figure6(b). The amount of energy that is consumed in the transmission of data packets from a specific node to the sink or even to an intermediate node on the link has a strong relationship with obtaining a good steady state of the wireless channel between two partitioning nodes. Therefore, routing based on statistical parameters that define the transmission channel is more efficient than a routing algorithm that is based on a straight-forward hop count.Figure12 shows the influence of increasing the link quality on the energy consumption when solving the optimization problem using the constraints of the transmission range, the optimal number of hops, and the integer decision variable. It appears that direct transmission always consumes 10 times more energy than multi-hop communication does whenever the transmission range increases or decreases, because the distance between the source and sink is fixed, taking D=150 m, for example. In multi-hop communication, the amount of energy that is consumed by the optimal aligned partitioned route globally decreases whenever the probability of the link efficiency estimation increases. To understand this behavior, that is, the increase, consider that the probability of the wireless link estimation will control to reduce the packet error rate by improving the SNR, by decreasing the distance between two adjacent nodes. This construct leads to deploying or waking a new node in the network, which then increases the network density deployment. The increase in the link quality implicitly assumes that a new aligned node on the partitioning route has a relatively high duty cycle that can determine the recent state of a wireless channel to each node, to transmit or receive packets, while other unaligned nodes implicitly save energy consumption by turning their radio off. Each node obtains link quality information about its neighbors, which provides a basis for establishing the solution of minimizing the energy consumption. Figure 11 illustrates the energy-limited node network scenario of an event-reporting scheme that assumes that the distance between the occurring event and two sensor nodes N1 and N2 are equal to 5.21 unit distance (ud) and 3.21 ud, respectively, the distance between each two adjacent nodes being nearly 12.45 ud. In this case, if the event is reported by N2, then the number of hops from N2 to the sink is five. When the event is reported by N1, the number of hops is more than five because the increasing quality of the wireless channel provides conditional controlling of the wireless sensor node density; the number of hops required to report an event does not increase when new nodes are deployed. The results obtained when partitioning the aligned nodes are seen in Figure 6(b). The energy consumption decreases with the increasing estimation of the link quality when satisfing the constraints on the number of hops that are required to report the event, which does not exceed the intermediate transmission radius, as seen in Figure 12 (where the amount of energy decreases by the aversion-serrated shape).Figure 11
Event reporting scenario in WSNs with increasing deployment nodes.Figure 12
The average amount of energy required to report an event under integer optimization programming.Figure13 depicts the energy efficiency of the WSN when solving the optimization problem by optimizing both the energy consumption and the PRR. The figure shows that the lifetime of the wireless sensor node increases when the packet travels along a number of partition routes which are estimated with an efficient link quality that connects the sensor nodes in the network domain. This increasing lifetime demonstrates that each sensor node unaligned on the partition route will enter a sleep state once because there is no in/ongoing transmission; it will otherwise enter the wakeup state whenever it is aligned in the partitioned route.Figure 13
The maximization of the lifetime under integer optimization programming. (1) Upper-bounded lifetime. (2) Node-density control. (3) Partitioning link quality.Unlike the proposed algorithm, the node density control algorithm [7] defines the reporting of the lifetime as a noncumulative function that depends on the total number of events that are detected by a network comprising of N nodes given as
(35)lifetime=energyconsumptionaveragenumberofevents.This procedure means optimizing the lifetime because more nodes are deployed at the same time. We have given an example to discuss the results. Consider that there areN nodes deployed along a highway to monitor the traffic cars that are present in the camera FOV. The routing from the source to sink during a specified period of time is given by thelengthoftrajectory/thevelocityofcar, which is 4.10 s with an acceleration of 600 m/s. According to kinematic equations, the distance that would be displaced during this period of time is 50.4. Suppose that the number of deployed nodes is 10. Then, the hop distance is 5.04, and therefore the lifetime is nearly 0.54 s. Whenever the period of time increases, the lifetime will decrease because of the inefficiency of the regular deployment of nodes, which is performed to keep track of the events and to route the report of the occurring events. On the other hand, the proposed algorithm designs a more efficient regular partitioning topology by performing link measurements during the times when nodes are awake for transmission or reception of events, with very little extra energy spent.Unlike the upper bound algorithm [8], the proposed algorithm uses the partitioning optimization to define the bounds on the lifetime of the sensor networks by discovering the independence of the source behavior, the partitioning region, the normal-log path loss modeling, and the residual energy. The proposed model achieves more energy efficiency than the two existing algorithms, namely, the node density control for maximizing the lifetime and the upper-bounded lifetime algorithms, which perform at approximately 67.91% and 96.91%, respectively.Figure14 shows the total power consumption in the network with four models that perform multipath routing algorithm equally. As expected, the proposed model performed better compared to ECMP and MCMP, which results from the fact that both the ECMP and MCMP models are deterministic zero-one problems in which all of the objective functions and constraints are linear. Moreover, the number of constraints actually presents as 2|N[ι]|+2, where |N[ι]| defines the number of sensor nodes in the networks. Therefore, the size of the search space will increase proportionately to the increase in the node density. Thus, it is obvious that whenever the number of nodes increases, finding the optimal multipath becomes too large for acceptable computation time. The search method for finding multipaths from the source to the sink that support QoS requirements is solved by the Balas algorithm, which is based on a random selection for the node at each next hop until the sink is selected. Consequently, the ECMP model can achieve more power savings, which are approximately 43.41% compared to the MCMP model because the MCMP has used 15.45% more multipath routing than ECMP. These results mean that the ECMO algorithm supports QoS requirements in sensor networks based on well-defined QoS constraints to avoid any exhaustion of energy that occurs when delivering the packets along the selected multipath.Figure 14
The power consumption comparison.Figure 15
The minimization end-to-end delay under integer optimization programming.Unlike both models, the proposed model routes the information over the optimal number of hops from the source to the sink. The strength of the proposed model lies on the fact that it accomplishes a trade-off between the optimal number of hops and the minimum energy consumption by selecting a path with the optimal number of hops. The proposed model depends on a new technical search method for selecting multipath routing based on Lagrange multipliersμ for given two nodes with an optimal number of hops. Then, it makes a transformation of the constrained optimal path problem to the objective function of the energy consumption equation (22), using the level cut off method. Therefore, this transformation for the power consumption will include the optimal solution, as depicted in Figure 8, which caused the proposed model to achieve more power savings (approximately 74.42% compared to the MCMP and ECMP models).The power consumption for ReInForM for each successful packet received is given byNs∑i=0k-1(1-pe)i=(1-(1-pe)klog(1-r))/elog(1-(1-pe)k), where k is the number of hops, and Ns is defined as the number of transmission multipaths for each successfully received packet, which can be expressed as Ns=log(1-r)/log(1-(1-pe)k), where r defines the reliability of the transmission channel rate. Therefore, the ReInForM protocol consumes more power than the other models because when there is increase in 1-pe, the ReInForM protocol will demand more multipaths to transmit the packet with desirable reliability.


## 4.2. The Influence of Estimation Link Quality on the Delay

To address the delay constrained environment, a comparison is made between the single hop and the multi-hop methods presented under delay constraints for the delivery delay, which is well approximated by the proposed model (which represents the behaviour of each node). Figure15 indicates that the benefits of multi-hop communication are eroded by the delay under delay-constraint. The figure shows the expected average data delivery delay from the source to the sink versus the probability of the estimation of the link quality. The graph of the delay is a concave function. Although a good steady state of the transmission varies, the delay is almost of the same pattern, and therefore a good steady state satisfies the constraints, and the minimum delay is a global optimization value.The figure demonstrates that the delay decreases when the packet travels along links with estimated efficiency that connects the sensor nodes in the network domain. Because of the increasing probability that a link will increase the sensor node deployment, this relation results in minimizing the delay by applying the integer optimization problem constraint in which the end-to-end delay is constrained to find the optimal aligned partitioned route.In addition, for a comparison in terms of the average end-to-end delay, both the ECMP and MCMP models perform equally with little difference. Because the multipaths selected by the two models are different in terms of the number of hops, as illustrated in Figure16, it appears that the ECMP model uses a smaller group of longer multipaths than the MCMP model. Therefore, the MCMP model tends to consume more power than the ECMP, which lowers the average end-to-end delay. The similarity of the performances of the ECMP and MCMP justifies that the trade-off between the power consumption and the average end-to-end delay is impacted by the number of selected multipaths, which reveals that the ECMP model uses a smaller or longer multipath resulting in lower power consumption with a higher average end-to-end delay.Figure 16
The average end-to-end delay comparison.In contrast, the proposed model outperforms the others models by using its preferred selected multipath with an optimal number of hops. This result reveals, in general, that the proposed model uses the multipath with the optimal number of hops compared to the other models. Therefore, the proposed model is more likely to lead to a lower average end-to-end delay.


## 4.3. The Influence of the Estimation Link Quality on the Packet Received Ratio

PRR is considered to be one of the most important metrics in real-time WSNs applications. This metric indicates the number of packets that meets the specified QoS requirements. The proposed model has extended the investigated network performance by studying the influence of the optimal hop number on the relationship between the SNR and the packet delivery ratio (i.e., the ratio of the received packets to the attempted packet transmission). Figure17 illustrates the relationship between PRR and SNR for the various numbers of hops for the integer optimization problem constraint in which the energy consumption is constrained. For the single hop, multihop, and optimal number of hops, the figure demonstrates that the optimal number of hops along a selected partition path achieves a good PRR. In the experiments, PRR was in the range of 51–90%. This result was the optimal rate for the optimal energy consumption at which there is a sufficiently strong signal reception strength, which had an SNR value in the range of 1–25 dB. The single hop of the selected partition path that consumed more energy had a PRR of 98.81%. Additionally, the multihop of a selected partition path PRR was in the range of 81–99%. All of the models perform equally in terms of the PRR for the reliability of transmission channels, as illustrated in Figure 18. To have a close view of the PRR, the curves of all of the models show the PRR on a log scale. As expected, the proposed model achieves the best performance of the PRR, which is approximately 96% compared to the other models, the ECMP, MCMP, and ReInForm, that achieved 94%, 92%, and 88%, respectively. Usually, the packets reception ratio increases logarithmically whenever the reliability of the transmission channel rate increases, because of ensuring more packets to deliver to the sink in a successful manner with a small expiring ratio for the packets lost.Figure 17
The relationship between the PRR and the SNR for single hop, multihop, and optimal hops.Figure 18
The packet success ratio comparison.


## 5. Conclusions and Future Research

WSNs involve potential real-time applications in a wide variety of scenarios. Most of the typically envisaged applications are in real environments, such as monitoring, surveillance, and security, in which there is a need to report alarms or warning messages to the sink or central processing until whenever a certain sensed parameter exceeds a threshold value. Therefore, providing sufficient information about the links between sensor nodes is considered to be an important issue in designing an efficient network topology control for routing when a demand arises. The purpose behind a regular and more controllable network topology is to find the optimum transmission range for the nodes given some specifications on the sensor network (e.g., the energy consumption, lifetime, or throughput).In this paper, a routing metric to determine the optimal path and to select the intermediate sensor nodes for routing packets from a source to a sink was introduced. The metric prioritizes the sensor nodes according to the factors of link quality based on a generic routing protocol. Moreover, the paper highlights the QoS constraints, such as the node density and physical parameters, which are considered in an efficient routing protocol during its design. The results demonstrate that the proposed metric improves the PRR from the source to the sink, increasing the lifetime and minimizing the end-to-end delay. The increase in the lifetime was demonstrated by the observation that each sensor node that was not aligned with the partition route enters a sleep state once because of no in/ongoing transmissions; otherwise, it enters a wakeup state whenever it is aligned with the partitioned route.In future studies, we recommend investigating the effectiveness of an accurate energy model of a receiver at the physical layer on the performance of a MAC and network protocols under the collision mode, where the capacity of the WSNs is limited mainly by concurrent packet transmission. Many studies are based on the assumption that the sink can simultaneously extract or retransmit the signal from multiple intermediate sensor nodes, which often leads to useless collisions and a significant degradation in the network performance such as the throughput. Therefore, the cross-layer design recommended as a methodology requires further investigation for the multiple packet reception model because the interaction between the PHY and the MAC layers significantly improves the throughput, the capacity of the WSNs, and reliability decisions.



---

*Source: 497157-2013-05-16.xml*