This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.
A Composed Energy Aware Metric for Wireless Sensor Networks
A network of sensors be composed of a lot of nodes, deployed and distributed to collect data from their environment. Sensor Networks functionality appears when sensors cooperate to each other, which means, each sensor have a limited functionality, and they can accomplish a few processing or monitoring functions but when they cooperate with the other sensors, they can do a lot of functionality in details.
Like as the other networks, Sensor Networks can be deployed with wireless nodes, which make the ability to remote connection, so called Wireless Sensor Networks. Figure1.1.2. In the past years, Wireless Sensor Networks have been used for diversity applications such as battlefield surveillance, Forrest fire detection, Habitat monitoring, Smart Homes and so on. For instance in the smart homes, the sensors make intelligent decisions as to how to adapt, what changes to make, what actuations to be performed based on the transforming states of the environment. An example scenario could be the lights turning on when a person enters the room at night, controlling room temperature by switching the cooling/heating levels of an air conditioner etc (Ankit Mehta, 2005). 1.1.3.
One of the most important constraints on wireless sensor nodes is the low power consumption requirement. Wireless sensor nodes carry limited, generally irreplaceable, power sources. While traditional networks aim to achieve high quality of service (QoS) provisions, sensor network protocol must focus primarily on power conservation. They must have inbuilt trade-off mechanism that give the end user the option of prolonging the network life time at the cost off lower throughput or higher transmission delay (I.F.Akyildiz, 2001). There are several factors that influence the wireless sensor networks lifetime such as network topology, routing protocol, and sensor node design in point of hardware view. All aforesaid factors have been studied and developed by many researchers but there are still challenges to find out a robustness wireless sensor network in terms of power conservation. One of the most important of these factors is routing protocol in WSNs, which its main goal is, finding communication paths between nodes, and choosing the best path. In recent years, many routing protocols have proposed for WSNs, and implemented with different applications.
One example of a power aware routing protocol is the Directional Source Aware Routing Protocol (DSAP). The Directional Source-Aware routing Protocol (DSAP) was developed by Salhieh, Weinmann, Kochhal, and Schwiebert in 2001 (Salhieh, 2001). According to [Salhieih  etal, 2001], in DSAP, after finishing collecting the information from the neighbors and based on this information, the routing protocol decides which neighbor should receive the packet.
1.2 Problem statement
Directional Source aware protocol is one of the WSNs routing protocol which was developed by Salhieh, Weinmann, Kochhal, and Schwiebert on 2001 (Salhieh, 2001). This protocol is a local information routing protocol, which, each node only knows about its neighbor's information. Furthermore, each node transmits the packet to a particular neighbor, which is closer to the destination. Then the new node is in charge of the packet and, it will forward the packet by one of its neighbors again. This procedure will continue, until the packet reaches destination. Making this decision, which node's neighbor should be select to forward the packet, is based on a Directional Value (DV) parameter.
DV is a parameter that, represent the each node's geometric position in the network. Some metrics and methods were developed for DSAP, such as power aware metric (A.Salhieh, 2004) to prolonging sensor network lifetime. But there is still an issue in current power aware metric. Current power aware-DSAP metric most of the time takes the neighbor's node which has the most power with shortest path. Taking the particular paths causes to depleting energy in specific nodes in network and unbalanced power dissipation in network. Therefore, some nodes in the network stay untouched, whereas they could participate as a path to prolonging the network life time and also increasing the number of message delivery. If this problem is solved, the lifetime of the sensor nodes can be prolonged.
The objective of this research is to propose a new metric to be used in the DSAP protocol which will prolong the lifetime of the sensor nodes in the network. The metric proposed in this research could help balancing the network's node energy dissipation by using different nodes properly as the chosen path instead of using some nodes more frequently.
In this dissertation, the proposed metric is applied to the DSAP routing protocol in a 2-Dimentional topology with 4-neighbors. Although the protocol can be used by nodes with more than 4-neighbours, it will not be considered for this research. Furthermore, the 3-dimensional topology will not be considered as well. The proposed metric will be tested for a network with 12 nodes, and the source and destination are fixed. According to the basic DSAP which is based on only local information, we followed that rule in the new metric, too.
The proposed metric could prolong the lifetime of the sensor nodes used in the WSN. By prolonging the lifetime of the sensor nodes, a lot of information could be gathered and can be used by various types of applications such as, military, health, and environment. This can contribute to the well-being of the society.
1.6 Organization of the Dissertation
In the first chapter the overview of the research has been given. In addition, the objective, scope and significant were also given. In chapter 2, the wireless sensor networks technology will be explained in detail. In addition, the routing protocols used in the WSN will also be discussed. One of the protocols known as the DSAP will also be discussed in this chapter. In chapter 3, the discussion will be focused on the current DSAP and the last modification for energy awareness for DSAP. Later in the chapter, the proposed new metric will be introduced. The proposed new metric will be explained in details in chapter 4. After that, chapter 5 would be discussing about the simulation model developed to test the proposed metric. The result and discussion of the simulation will also be discussed in this chapter. Finally, the dissertation will be concluded in chapter 6, by giving the analysis of the results and the dissection for future works.
In this chapter, the overview of the research has been given. In addition, the objective, scope and significant were also given. In the next chapter the wireless sensor networks technology will be explained in detail.
CHAPTER 2 Wireless Sensor Networks
Wireless Sensor Network (WSN) can be said to be the latest member to the data networks family. A typical WSN would consists of a number of sensor nodes (can even be in thousands of them) (I.F.Akyildiz, 2001). All the nodes has separate sensing, processing, storage and communication unit. The position of sensor nodes need not be predetermined (Ankit Mehta, 2005). 2.1.1 shows an example of a sensor node. There are more than one type of sensor nodes that could be used. The size of the sensor nodes can be as small as the size of a grain or as big as the size of a typical shoebox.
The sensor nodes are used to collect data depending on the type of applications they are used for. The nodes can be used to collect data for military purposes, such as battlefield surveillance, or it can be used to collect data for monitoring the environment, such as for collecting temperature, or it could be used to collect data for health monitoring purposes, such as for monitoring heart beat.
After the nodes have collected and processed the information, they will transmit the required information to the computer (also known as the base stations) that collects the data (I.F.Akyildiz, 2001). The information is propagated to the base station via a radio transceiver or other wireless communications device using a pre-defined routing protocol.
There was an issue of compatibility of transducers for different network before the Institute of Electrical and Electronic Engineer (IEEE) developed a standard for WSN. As a result, in 1993, the IEEE together with the National Institute of Standards and Technology (NIST) started the initiative to design a standard for smart sensor networks. The general model for the Smart Sensor Networks is shown in 2.1.2. By having this standard, it is more easier for manufacturers to develop smart sensors and to interface those devices to networks (Lewis, 2004). An example of WSN design is given in (Ankit Mehta, 2005). Mehta (Ankit Mehta, 2005) used a middleware as shown in 2.1.3 in designing his WSN.
Each of the sensor nodes depends on an energy source, normally a battery, to supply the power in order for it to be able to function. Today, one of the biggest issues that the research communities all over the world try to solve is to prolong the lifetime of the sensor nodes. In order to achieve this objective, there have been many proposals such as using the hardware involved in the WSN, using directional antennas and one of the recent initiatives is to use power-aware routing protocols to be used by the WSN (Lewis, 2004).
2.2 Routing Protocols in WSNs
Before the types of routing protocol in wireless sensor networks are discussed, some challenges in wireless sensor networks will be considered in contrast with other traditional networks such as mobile ad hoc networks or cellular networks, as discussed in (Jamal N. AL-Karak, 2004).
The first challenge faced by the wireless sensor network is, the unfeasibility of having a global addressing scheme. Due to the relatively large number of sensor nodes, it is not possible to build a global addressing scheme for the deployment of a large number of sensor nodes as the overhead of ID maintenance is high. Thus, traditional IP-based protocols may not be applied to WSNs.
The second challenge is, in most applications of sensor networks, requirement is flow of sensed data to a particular base station in contrast to typical communication networks. However, physically sensors cannot prevent the other forms such as multicast or peer to peer. For instance, an application of sensor network which is supposed to gathered data and send to a BS. It does not need broadcast the sensed data to whole network. Therefore, it is considerable point that most be concerned to design of a protocol for sensor networks to prevent other forms of communication as much as they can. ??? Need more information here !
The third challenge is, energy, processing, and storage capacities are very critical consideration in sensor nodes. Therefore, a suitable resource management mechanism is tremendously required. The objective now is to prolong the lifetime of sensor nodes so that more information can be gathered.
The fourth challenge is, network topology. Almost the nodes in all application scenarios in WSNs are generally stationary after deployment except for maybe a few mobile nodes in contrast with traditional wireless networks that they are free to move. Therefore, the routing protocol needs to design properly for this kind of low mobility topologies. ??? Need more information here !
The fifth challenge is, variety of application of sensor networks with specific properties and requirements (i.e., design requirements of a sensor network change with application). For instance, the challenging problem of low-latency precision tactical surveillance is different from that of a periodic weather monitoring task. In other words, designing routing protocols for sensor networks are very application demanded because of this diversity. ??? Need more information here !
The sixth challenge is, data collected by many sensors in WSNs is typically based on common phenomena, so there is a high probability that this data has some redundancy. ??? Need more information here !
Based on the challenges faced by the sensor networks, many researchers have studied, and presented variety of routing protocols, which are suitable to be implemented with wireless sensor networks as mentioned in (Jamal N. AL-Karak, 2004). All these routing protocols, have either dealt with one or more challenges mentioned in the previous paragraphs.
Generally, routing protocols in WSNs can be classified into two main categories with respect to its network structure or the protocol operation. In the Network structure category, there are three subcategories, namely: flat, hierarchical, and location based. In the protocol operation category, the WSNs routing protocols can be categorized in five subcategories, namely, Negotiation-based routing, Multipath-based routing, Query-based routing, QoS-based routing, and Coherent based routing. 2.2.1.?? shows the classification of routing protocols in WSNs based on these two categories.
Furthermore, the routing protocols can be classified into another three categories, depending on the route determination, i.e.: Proactive routing protocols, Reactive routing protocols, and Hybrid routing protocols (Ilikhan, 2008). 2.2.2.?? shows the classification of routing protocols in WSNs based on its route determination.
In flat networks, all nodes are in the same level and play the same role. The sensing task is performed with the collaboration of all nodes. Typically, a flat routing uses base BS(s) to send queries to certain region, and waits for the reply from the node(s) within that region. In this network, the routing protocols would find the paths by using the multi-hop query dissipation from the source to the destination, or from destination to the source. An example of a routing protocol based on this network is Sensor Protocols for Information via Negotiation (SPIN).
Heinzelman et al. in (Kulik, Heinzelman, & Balakrishnan, 2002) has proposed a family of adaptive protocols called Sensor Protocols for Information via Negotiation (SPIN) that is based on negotiation between nodes in the network. In this protocol, each node will share its information with the other nodes. The negotiation is handled by the meta-data by aiming for each node in order for it to know about available resources and data from its neighbors. The negotiation also will ensure that the node will only transmit the data when it is necessary and to ensure that it will never lose the energy unless through transmissions.
The SPIN operates with three kind of messages; ADV, REQ, and DATA. The ADV will be broadcasted by a node which holds the new data. After that, the neighbors, who are interested about that data, will response to the message by sending REQ message to the source node. After the request message has been received, the source node will send the DATA message to the interested node. This procedure is shown in 220.127.116.11.1.
As shown in 18.104.22.168.1, node A starts the procedure by advertising data to node B (a). Node B responses by sending a request to node A (b). After the receiving the requested data (c), then node B sends out advertisements to its neighbors (d), who in turn send requests back to B (e-f).
Scalability is one of the challenges in wireless sensor networks. A hierarchical architecture for wireless sensor networks is one perfect solution to address this scalability issue and also in increasing the network life time. In hierarchical routing, nodes with higher energy will be used to process and transmit information while other nodes with low energy are used for sensing. Hierarchical routing is called cluster-based, because the nodes are clustered together and has a cluster head (CH) which is assigned a special task. CHs in each cluster of network aggregate sensed data from sensor nodes and transmit these data to BS rather than for each sensor node to send sensed data directly to the BS. The CHs normally are not static; they change frequently depending on their remaining energy. Hierarchical routing is an efficient routing to increase the scalability, network lifetime, and energy efficiency. Low Energy Adaptive Clustering Hierarchy (leach) is an example of routing protocol under this category.
Low Energy Adaptive Clustering Hierarchy, so called LEACH, was developed by Heinzelman, et. al (Akayya & Younis, 2003) in 2000. LEACH is a self-organized, hierarchical routing protocol, which selects a few nodes as cluster heads (CHs) randomly in networks. This random election causes to aid load-balancing in the network. Compressing data by the CHs is an advantage in LEACH to reduce the amount of information that must be sent to the base station. In other word, nodes in each cluster, sends the data to CH and then CH compresses the data to aggregated packets, and send it to the base station. By doing so, a package of data be sent to base station rather than sending data frequently from CH to base station. Furthermore, the data collection is centralized in LEACH and is performed periodically. However, the role of CHs rotates randomly for more efficient energy dissipation in network.
2.2.3 Location based
In location based routing, sensors are declared by their locations. That means each node is addressed by its location. By doing so, some calculation such as estimation of distance between nodes or computation of cost of path, becomes much easy. Location addressing in nodes depends on the type of network and protocols, for instance, in some routing protocols, the node's location information addressed by a low-power GPS receiver (Rodoplu, 1999), and some protocols addressed fix location information to their sensor nodes during the network initialization. Furthermore, the most location based routing protocols are designed for mobile ad hoc networks but this kind of routing can be used for stationary networks as well (SALHIEH, 2004) (Nath & D.Niculescu, 2002). However, some of these protocols such as (Nath & D.Niculescu, 2002) were not suitable for wireless sensor networks, because they are not concerned about energy consumption.
Since the sensor nodes knew about their locations in location based protocols, therefore, we can make the network to some part geographic regions. Geographic and Energy Aware Routing (GEAR) was developed by Yu et al. in 2001 (Yu, Govindan, & Estrin, 2001). GEAR uses the geographic information to disseminating queries to proper regions. GEAR's basic idea derived from directed diffusion by sending interests to a certain region instead of sending the interests to whole network. This means, reduction the number of interests, thus, more energy conservation than directed diffusion.
There are two kind of costs in GEAR; estimated cost and learning cost. Each node computes a combination of residual energy and distance to destination as estimated cost. In some occasion there are holes in the network when a node does not have any closer neighbor to the target than itself. Then, the learned cost re-estimates from estimated cost to handle these holes. The estimated cost and learned cost are equal when there are no holes.
Routing algorithm in GEAR consists of two phases: Forwarding packets towards the target region: in this phase, when a closer neighbor to the destination exists, the next-hop node which is closer to destination will be picked up. If the all neighbors are further away, which means there is hole, then, the learned cost will be used to pick next-hop node rather using the estimated cost. Disseminating the packet with in the region: When the packet has reached the region, it can be disseminated in that region. There two ways for that dissemination; recursive geographic forwarding and restricted flooding. The restricted region is used when the sensors are not densely deployed, but in case of high-density networks, recursive geographic flooding will be used. The recursive flooding divides the region into four sub regions and four copies of the packet (22.214.171.124.1, illustrates the splitting regions), then this task continues until the regions with only one node left.
2.2.4 Power awareness routing protocols
126.96.36.199 Energy-aware routing protocol (EAR)
As we mentioned in routing protocols in WSNs section, one of the most challenges in routing protocols is the energy consumption. Shah et al. in 2001 (Shah & Rabaey, 2001) developed a new routing protocol, called Energy Aware Routing (EAR). The EAR is very similar to directed diffusion (Intanagonwiwat, Govindan, & Estrin, 2000) in some parts, but they are completely different in path selection. The EAR finds multipath between sink and source, and chooses the many paths based on a probabilistic fashion. In the other hand, directed diffusion selects a single optimal path for communication. The main idea for Energy Aware Routing protocol was to prevent the network to be partitioned by choosing multipath, rather than using one single path and depleted some nodes and partitioned the network.
There are three phases in the EAR: setup phase, data communication phase or data propagation phase, and route maintenance phase. In the setup phase, the routs will be discovered by flooding the interest to the network and find all possible routes between source and destination. In addition, the routing tables build in the setup phase and all the paths cost will be calculated and inserted to the routing table. In this phase all the cost of paths calculate and write on the routing table:
, is the cost between node and node. The Metric is an energy metric, that calculates the metric cost by communication energy and residual energy of each nodes i and j. Furthermore, the paths with high cost will be discarded, only the path with low cost will add to the routing table. Then will assign a probability inversely proportional to the cost, for each of the neighbors in the forwarding routing table (FT):
The cost of node with average of the probability of selecting neighbors in the forwarding table and cost of neighbors, calculates by this formula in below:
The data communication or propagation phase will send the packet through the network from source to the destination by choosing the neighbors who has the same probability with the probability in the forwarding table, until the packet reaches to the destination.
The third phase, which is maintenance phase, runs a localized flooding to updates the all paths.
188.8.131.52 Decentralized power aware routing protocol
In wireless sensor networks, communication has more energy consumption instead of the other operations such as processing, according to the research in (Pottie & Kaiser, 2000). This high cost of communication was encouraged to make decentralized protocols for WSNs. The decentralized protocols share processing tasks to each node in the network rather than centralization processing. This means each node can process and compute their local available information. Decentralization aims to reduce the number of control messages, which need to be sent in the network to discover routes. However centralized protocols have advantages to find the optimum paths because they gather global information, but in point of energy consumption, the decentralization because of reduction of number of control messages might be a good solution. In (Salhieh, 2001) (Salieh, Weinmann, Kochhal and Schwiebert) developed a decentralized routing protocol for stationary topologies to prolonging network lifetime. The routing protocol was completely based on local information that is available to each node from its neighbors. Furthermore, base on the local information each node capable to make decision to forward messages to final destination. In this local based information protocol, consideration was on the only local point of view in the routing protocol, hence, there was limited information that each node can got from its neighbors (SALHIEH, 2004). All information is as follows:
* Cost of communication and distance between a source and its neighbors.
* Cost of communication and distance between a node and the base station.
* Number of neighbors.
* Power remaining at the neighbors.
According to these limited local information, current routing algorithms was not proper. Therefore, in (Salhieh, 2001) developed a new routing algorithm, which so called directional source-aware routing protocol (DSAP).
DSAP was a directional routing protocol which means, each node needs to know about the direction of destination to forward a packet to destination. 184.108.40.206.1. We will discuss more about DSAP and its metrics in next chapter 4.
In this chapter wireless sensor networks is discussed and also routing protocols in WSNs reviewed in some aspects especially about power awareness. The DSAP protocol is introduced and in the next chapter the DSAP will be discussed in details.
CHAPTER 3 Directional Source aware routing protocol (DSAP)
According to categorizing the routing protocols based on route determination, there are three kind of routing protocols which are proactive, reactive, and hybrid. Proactive routing maintains routes to every other node in the network, thus a route can be provided immediately when requested. Regular routing updates impose large overhead, thus proactive is suitable for high traffic networks. Reactive routing maintains routes to only those nodes that are needed, in other words on-demand. Each host computes routes for a specific destination only when necessary. Thus, the cost of finding routes is expensive, since flooding is involved. This kind of protocol is good for low/medium traffic networks. Traditional reactive protocols find the best route and then always use that route, but that is not the best solution for a wireless sensor network. This kind of routing is not an efficient way of routing, since we want the protocol to be power aware and source aware. The third category maintains partial topology information of local hosts. Routing decisions are made either proactively or reactively (SALHIEH, 2004). Hence, regarding to issues in these three kind of protocols and also to finding out a suitable routing protocol for decentralizing, which we have discussed in previous chapter, a new routing protocol proposed in (Salhieh, 2001), so called directional source aware routing protocol (DSAP).
As mentioned earlier, DSAP is a directional routing protocol, which means each nodes need to know direction of destination to forward the packet in that direction. Since the DSAP is based on only local information and nodes need to know about their directions, thus, each node needs to know about its location in the network and other node's location. For achieving to this goal, Directional Value (DV) system is defined to identify each node's location in the network.
Directional value is a unique identification value that uses to identify location of each node in the network. There are some properties for DV as follows (SALHIEH, 2004):
* Each node has a unique ID.
* Each ID gives how far the node is from the network perimeter in each direction.
* Each node can compute the relative direction of another node from its ID.
In order to constructing the directional value, each node needs has fixed number of neighbors, the number of neighbors are depend on the topology that is used in the network. For instance, a network with 2D-4 topology, which means 2 dimensional with 4 neighbors, each node has 4 neighbors that they are representing directions that the node can route through them. 3.1 illustrates some types of 2D topologies in directional routing.
The directional value of each node is how far a node is from the edge of the network in each direction. The DV for each node is unique and can be used as an ID number which is necessary to use for routing. 3.2 shows a 4 Neighbor topology, which node-s has 4 edges D-0, D-1, D-2 and D-3 to 4 neighbors, respectively to neighbor-0, neighbor-1, neighbor-2, and neighbor-3. Therefore, the ID of node-s would have an identifier of (). This means that there are nodes to the edge in direction D-0, in D-1, in D-2, in D-3.
In 3.3 a sample of network T-4N with 11 is showed, for example in this , node (1, 1) would have an identifier of (1, 1, 2, 1). This means there is 1 node to the edge in direction 0 (left), 1 node in direction 1 (up), 2 nodes in direction 2 (right), and 1 node in direction 3 (down).
Since each node knows about their location and also about their neighbors' location by directional values, the DSAP algorithm (Salhieh, 2001) (3.4) is ready to start to route messages from source to destination. The basic scheme of DSAP algorithm is, destination node identifier subtracts from source node identifier. This subtracting will come out a new DV, then the negative directions in this new DV will be eliminated and the positive directional numbers would be used as possible of route to forwarding the message. The source's neighbors with positive directional number will be subtracting again from the destination node identifier. The same as the source node, the subtracting comes out a new DV for the each neighbor, then all the directional numbers in new DV for neighbors will be add together and the neighbor with smallest value will be choose as the next hop. Furthermore, if some nodes have the same DV, then one of them will be choose randomly. The chosen neighbor node assumes as the source, and this process repeats until sum of directional numbers in new DV being 0, which means the message reached the destination.
For instance, if we consider the node (1,1) in , as the source, and node (2,3) as the destination. The following is the procedure that a message will transmit from the source to the destination:
First of all, source node (1,1) with (1,1,2,1) subtracts from the destination node (2,3) with (3,2,0,0). So, source - destination = (-2,-1,2,1). The nonnegative directional numbers consider as possible routes, which are node (1,2) in direction 2 (right) and node (2,1) in direction 3 (down).
Second, the directional value of each possible node for routing will subtract from destination DV. In this case, (2,1,1,1) - (3,2,0,0) = (-1,-1,1,1) , then the new DV directional numbers add to gather, which makes the value of 4. The same process performs for node (2,1), (1,2,2,0) - (3,2,0,0) = (-2,0,2,0), after adding the directional numbers, the DV for this node is 4. The next step is comparing between two DVs value which are exactly the same in this case with value of 4. Therefore, the algorithm chooses one of these nodes as next hope, and will forward the message to it. If we assume that the node (2,1) has been chosen, this node will considered as source in the algorithm and the same process will be perform until the DV of 0.
The basic scheme of the DSAP is not an efficient power aware routing because the routes are chosen without power consideration. Therefore, in (Salhieh, 2001) the authors, developed a new metric for DSAP, which was a power aware metric. This metric will be introduced on the next section.
3.1 Power aware DSAP
In view of the fact that the power consumption is extremely important in wireless routing protocols, therefore, taking care of available energies on each node in network must be considered in directional source aware routing protocol too. For reaching to this goal, several power metrics were developed by Salieh and Schweibert in 2004 (A.Salhieh, 2004). The metrics all are based on the basic scheme of the DSAP algorithm and also they are using the local information available in the network, which has been mentioned in chapter 2, accordingly, each node knows about its neighbor's residual energy. Also, since DVs of each neighbor is computable by source nodes then calculating the number of hops is possible.
Developed metrics are included of power only, Directional Value only, DV and power, the sum of power and directional value, number of hops, the cost of route and number of hops, and combination of all them.
3.1.1 Power Only
In this metric, DSAP calculates the DV of source node to determine the positive directions and then forward the packet to the neighbor with maximum power available. The issue is, the metric may take longer paths because of power, therefore, causing energy more depletion in the network.
3.1.2 Directional Value Only
The Directional Value Only considers only the DV of its neighbors with respect to the final destination, which is exactly the basic scheme of DSAP algorithm. Since this metric does not care about the energy available in the neighbor nodes and only makes decision for forwarding the packet based on only DV, hence it may takes paths with short length but very costly. Therefore, it is not a power efficient metric.
3.1.3 DV and Power
The combination of two metrics, Directional Value and Power is another metric that was developed by Salieh and Schweibert (A.Salhieh, 2004). It is energy efficient metric that considered the maximum available power and minimum DV when picking which node route to take. Rather than picking the node with lowest DV or maximum power, the DV divided by the power available at that node. The smallest value of this power-constrained DV is the path that is chosen. The details of algorithm shown in 3.1.3.
One issue in this metric is, in some cases the metric choose the longer path because of the available power dictates. Therefore, it may cause unbalanced energy dissipation in the network.
3.1.4 DV and Sum of Power
This metric is approximately the same as the DV and Power is, but instead of looking at the power at the neighbors of the source, it looks one hop beyond these neighbors from each neighbor. By doing so the protocol may have a better choice in picking the next route.
3.1.5 Number of Hops Only
According to existing information from DV, the number of hops can be calculated. The number of hops gives a maximum and minimum number of hops for each direction. This metric uses the average of those two numbers to make a choice on routing the packet. The neighbor with minimum number of hops will be chosen to be forward the packet.
3.1.6 Hops and Cost
This metric, uses the number of hops and from number of hops, the cost of routing in each direction can be calculated. The procedure starts by picking up the first hop and multiply by the number of neighbors, it is because of when a node transmits a packet to another node, all neighbors of the source node will received the packet, which means cost of that route. The metric using the average of the number of hops and cost to choosing the next node that the packet must be forwarded.
3.1.7 Hops, Cost, DV, and Sum of Power
In this metric which obliviously is a combination of all metrics. In another words this metric uses of all available information in the network. First of all, the value of the number of hops and cost estimate then the DV and sum of power at the neighbor will be calculated. Lastly, the node with minimum value of ratio between those two values will be chosen the packet to be forwarded.
According to simulation results of research in (A.Salhieh, 2004), for all metrics have mentioned. The DV and Power and DV and sum of power are the most efficient metric to prolonging the lifetime of nodes in the network. These metrics extend the network lifetime approximately % 29 and % 31, respectively rather the basic scheme of DSAP which is metric with DV only.
3.2 Modified DSAP
Recently Samir, Marc and Bachar developed modified DSAP (MDSAP) in (El-Haddad, Girod-Genet, & Hassan, 2007). They addressed to the issue of current DSAP limitations, which was choosing path with maximum power even it is not the shortest path in some case. Furthermore, they addressed to choosing the different path instead of using one path always. MDSAP basic idea was to categorize the message in the network to three categories which were included: high priority, medium priority, and low priority.
High priority messages in MDSAP protocol are forwarded to next node with highest power. In high priority message case, reaching to destination is the goal and the protocol does not care about path long. Therefore, the message routes with longest path but with most energy.
MDSAP chooses the shortest path as long as the power is over a certain threshold, when the message is a medium priority message. But when the power is blew the threshold the path will changed to second shortest path that power of nodes are over the certain threshold. There is an emergency case in this situation when all neighbor nodes are below the threshold. In this case, the message will be changed to urgent message and the path with maximum power will be chosen.
Low priority messages rather than high priority messages always takes the shortest path, no matter what is the power of the nodes.
MDSAP for approach to get its neighbor power information, the neighbor sends three types of warning message. These messages are the following (El-Haddad, Girod-Genet, & Hassan, 2007):
* A debug message labeled “Node OUT of power” is sent when the power of the node is equal to zero.
* A message labeled “NODE is half-power” is sent when the remaining power level reaches 50%.
* A message labeled “Message is lost at this Node” will be displayed when all the neighbors of a given node run out of power.
According to simulation results in (El-Haddad, Girod Genet, El-Hassan, & El-Nabbouch, 2008), MDSAP in contrast with regular DSAP, improved the network lifetime, and more performance in reaching a message to final destination. The results shows (table 3.2.1 ) when MDSAP using only high priority the network life time 22% increases, the prolonging of network lifetime for medium priority, low priority, and random priority are 55%, 77%, and 88% respectively.
Compared with the regular DSAP
Table 3.2.1: MDSAP comparison results with Regular DSAP
Source: (El-Haddad, Girod Genet, El-Hassan, & El-Nabbouch, 2008)
However the modified-DSAP increasing the network lifetime in contrast with regular DSAP but it needs categorized messages in network, therefore this algorithm may not be efficient if an application needs has a network with a fix kind of message. In other words, MDSAP is an application demand protocol.
3.3 Proposed power aware DSAP metric
In this dissertation, we presented a combined metric includes of current power aware-DSAP metric and a new metric. The idea is, when a node has been used one time before in path, it will take a new metric instead of using the current power aware-DSAP metric. Otherwise, it takes the power aware-DSAP metric and finds the node to route. When the new metric be chosen, the neighbor node will tell a lie about its remaining energy to its parent source node, then the new metric evaluate by this untrue energy value. It could decrease the chance of taking that node, which has been taken one time before. This new metric would call white-lie, because of the lie can help the network to be survive for more time. Hence, the network life time will be increase, and also other nodes will be use properly in path to increase the chance of message delivery. The proposed metric will be explained in detail in chapter 4.
In this chapter, the Directional Source-Aware Routing Protocol (DSAP) discussed in detail. Power awareness metrics for DSAP mentioned and according to the simulation result in (A.Salhieh, 2004), the DV and Power metric was the best metric for prolonging life network lifetime. Later on, Modified DSAP is given, which was a new algorithm for DSAP to extending network lifetime. Finally, the new proposed metric discussed to prolonging network lifetime and increasing the number of message delivery in DSAP protocol.
CHAPTER 4 Proposed power aware DSAP metric
After studying the all current metrics and algorithm in DSAP, limitations such as unbalanced power dissipation in Power-DSAP and application demand in MDSAP, the time is to propose the new metric power aware for DSAP protocol. The basic idea is when a node has been used one time before in a path. It will take a new metric instead of using the current power aware-DSAP metric. Otherwise, it takes the power aware-DSAP metric and finds the node to route. When the new metric be chosen, the neighbor node will tell a lie about its remaining energy to its parent source node, then the new metric evaluate by this untrue energy value. It could decrease the chance of taking that node, which has been taken one time before. This new metric would call white-lie, because of the lie can help the network to be survive for more time. Hence, the network life time will be increase, and also other nodes will be use in path to increase the chance of message delivery. This new proposed metric avoid to broadcasting control messages or categorizing messages in the network rather than the MDSAP.
This proposed metric for DSAP, is to determine the directional value for each neighbor nodes which are supposed to be chosen in the next hop. Hence, if the neighbor node has been chosen one time before, therefore the directional value for that node will be evaluate with proposed new metric, otherwise, the metric DV and Power will be chosen to calculate the directional value. Then finally as the DSAP protocol routine the directional values for all positive direction neighbors of source will be compared to be select the one with minimum directional value. Of course in case if DVs were equal, then one node will be chosen randomly.
4.2 The proposed metric algorithm
In the proposed metric algorithm as shown in 4.2.1, the neighbor node presents their residual energy less by dividing its power with an α value, if the neighbor has chosen one time before. By doing so, if the DV value of the neighbor with untrue power was less than the other neighbor(s), then the node with untrue power will be chosen. Then the White-lie flag which is a counter to count the number of selection a node will be changed to 0.
The White-lie flag changes to 1 after the source node selected the neighbor node for the next hop. Furthermore, the White-lie flag is implemented for each node to count its neighbor number of selection. Therefore it is completely based on local information without broadcasting control messages. Because each node knows that last time which neighbor was chosen based on its White-lie flag.
For instance, consider a network 2D-4 with 12 nodes (4.2.2). The network wants to forward a packet from source node 4 to destination node 7. The proposed metric DSAP protocol starts with as regular procedure in DSAP basic scheme which is to evaluate directional value for all source neighbors.
In this case, (0,1,3,1) - (3,1,0,1) = (-3,0,3,0) , therefore, positive directions are possible neighbors to forward the packet. Node 0 in direction 1 (UP), node 5 in direction 2 (Right), and node 8 in direction 3 (Down) are the possible neighbor nodes to forward, hence, DV of these nodes will be subtracted from DV of destination to evaluate each node directional value. For example, (0,0,3,2) - (3,1,0,1) = (-3,-1,3,1) = 4, the other neighbors will be subtracted as well, value 2 and 4 for node 5 and 8 respectively. In next step, the DV values should be divided by their nodes residual energy as regular DV and Power metric, but the difference is here between new proposed metric and current metric, because, in proposed metric the neighbor node will be checked if it has been chosen before then DV value will be divided to an untrue energy instead of its real energy. In this case, if we assume node 5 has been chosen before which means the White-lie flag = 1, then the proposed metric will calculate the final value for this node. Final value for node 5 = 2 / (node 5 residual energy / α= 1.5), if the residual energy of node 5 was at a certain level that its final value was greater than the other neighbor node's final values, then the node 5 will not be chosen for this round. If the DSAP protocol acts as the regular power metric, the number of choosing of node 5 will be more than the proposed metric, therefore, this node will be energy depleted sooner. But, proposed metric prevents to choose node 5 before its energy at a certain level, through presenting its residual energy with untrue value. The node 5 is only an example, so this procedure can be done for other nodes as well.
The parameter α is a value to find the level of residual energy at node, however, the value α =1.5 is not the best value and needs to study more to find out an optimum formula to evaluate the best value for α.
After calculating the final value for node 5, the White-lie flag will be changed to 0 for node 5, because the next iteration, the node 5 has not been chosen therefore, must participate as a normal node with regular power metric. This procedure will be performed for other neighbor nodes as well.
In this chapter, the new proposed power aware DSAP metric is discussed in detail. The basic idea of the proposed metric and the complete algorithm is explained. Two new parameters defined in new proposed metric consists of White-lie flag and Alpha which are totally new in DSAP algorithm, regarding to implement the new proposed metric for DSAP. The next chapter the new proposed power aware metric will be simulated.
CHAPTER 5 Simulation model
Network simulator is a software program that can simulate computer networks with their all behaviors and properties, and producing results for analysis of the simulated networks behaviors. This kind of software can model networks with devices, traffics, or even environmental phenomenal that can be affect a network in a real world.
A various network simulator platforms are developed in recent years to model and simulate WSNs, such a TOSSIM, which is a part of TinyOS, SWAN which can be used for wireless networks or sensor networks. Simulators like ns-2have also been developed for multi-network simulation, wire or wireless.OMNET++ is, another network simulator software that has some useful sensor simulator frameworks like Castalia and Mobility framework.
In this research project, according to requirements that need to implement a stationery wireless sensor network for running DSAP protocol and also the new proposed metric, C++ could be an suitable option to do simulation. A brief introduction about C++ programming language and the reasons that C++ is chosen for this project, are discussed in next section.
5.1 C++ Network simulation
C++ is a middle-ware programming language that was extended from C by Bjarne Stroustrup in the early 1980s at Bell Laboratories. C++ provides capabilities for Object-oriented programming. However, C++ can provide both C-like style and Object-oriented style (Deitel).
C++ widely used as a programming language in software industry in different application such as application software, device driver, video game, and etc. These application varieties show ability and powerfulness of C++. In network simulation software area, C++ was used many times in different network simulators such as NS-2, OMNET++ as the main programming language.
In this dissertation as mentioned before the C++ is used as a language programming to simulate a wireless sensor network with DSAP protocol and the new proposed metric. In other words, a program is created by C++ to simulate the network instead of using traditional network simulators. The reasons that C++ is chosen as a tools for the simulation are as follows:
* Simplicity in implementation.
* The network scheme that should be simulated was not in large scale.
* The layer that simulation should be focused was in physical layer. Therefore it could be handled by a low scale program instead of using complicated modulation which used in other simulators.
* Graphical interfaces were not necessary.
* Results and analytical data can be gathered as text files and handle by MS Excel for displaying as graphs.
* Easy to debug because of simplicity.
5.2 Simulation assumption
According to the network that should be simulated, there are some assumptions and parameters to define. Some assumptions are defined to make simulation simple for implementation. They are listed below:
· The network simulates without any Base station node, which means the packets route internally between a source node to a destination node.
· Nodes in network know about their location and their neighbors location.
· Each node knows about available energy of its neighbors.
· The energy consumes by processing does not considered. Only communication including transmission and receiving cost considered.
· Source nodes do not receive the packet that they are forwarded to their neighbors when the neighbors want to forward to next hop.
5.2.1 Radio Model and initial energy
A simple radio model is assumed that is defined by Heinzelman, Chandrakasan, and Balakrishnan in 2000 (220.127.116.11, and table 18.104.22.168 ) (Kulik, Heinzelman, & Balakrishnan, 2002). Also, it has been used in (SALHIEH, 2004) for simulation of DSAP protocol. In this radio model, the radio dissipates to run the transmitter or receiver circuitry and for the transmit amplifier to achieve an acceptable (SALHIEH, 2004). The packet size in this simulation is k= 512 bit for all packets. is the amount of energy that node needs to spend to transmit a k-bit message to a distance d meters. The distance between each node in this network is d=15 m. The will evaluated from the formula in the below:
In the other side, to receive the k-bit message, will be evaluated from this formula:
The initial energy for each node is considered by 0.1 J. All nodes assumed to use this limited amount of energy and there is no external power source for the network.
5.2.2 Network and Nodes
The network that is simulated in this research is a stationary wireless sensor network included 12 nodes in 2D-4 nodes topology. The source and destination are fixed which are Node 4 as source and Node 7 as destination (22.214.171.124). The distance between source and its neighbors is d=15 m.
5.3 Network Simulation Implementation
In this part the simulation implementation is discussed in detail with some part of the source code. First of all, the flowchart of this simulation is drawn in 5.3.1 in below. The shown, the process of how does the network simulation act, precisely?
According to the flowchart, the simulation set some parameters when the program starts. These parameters are such as the initial energy, location of nodes in the network, node identifier for each node, and so on. Furthermore, the network in this program is defined as a 2 dimensional array with 3 rows and 4 columns which each cell of this matrix represents a node in the network. For instance, the Net is the node 7. In addition, the node identifier of each node of network also is defined as 2D array (5.3.2).
The energy and white-lie flag are initialized for the network by array. 5.3.3 the white-lie flag is an array with 12 cells, which each cell demonstrate the value of white-lie flag for each node, this array set by zero because when the simulation starts, the white-lie flag for first round is zero.
After all definition of parameters and variables in the simulation program, the simulation starts with a infinite loop, which is an “while(true)” command in this source code (5.3.4).
The next step when the simulation is running is to get the value of subtraction between source node identifier and destination node identifier. This progress is performed by the codes that are shown in 5.3.5.
5.3.5: the subtraction between source node identifier and destination node identifier.
DV_node is an array to store the neighbor nodes directional values, therefore node identifier of the positive neighbors of source will be subtracted by node identifier of destination node to compute the directional value for each neighbor node. In 5.3.6 codes is shown the details of process of this procedure.
After calculating the DVs for all positive neighbor nodes then the simulation will be performed the metric part for making the final decision which is choosing the next hop and transmission message to the next hop. This part of simulation is the only part that makes the simulation of the regular DSAP metric, regular power aware DSAP metric, and the proposed power aware DSAP metric, difference.
5.3.1 node power evaluation and message transmission
In this simulation program, the energy will be evaluated when a message transmit or receive by subtracting the ETx (for message transmitting) and ERx (for message receiving) from the total amount of energy in each node. In fact in this simulation, there is no actual message. But subtracting the ETx from the available amount of energy in the node is considered the node transmitted a message to another node (126.96.36.199.), and also, subtracting the ERx from the available amount of energy in the node is considered the node received a message (188.8.131.52.). As mentioned in section 5.2.1, the ETx and ERx are included the size of a message (or packet size k). 184.108.40.206. shown the initialization of the ETx and the ERx in the source code.
5.3.2 Regular DSAP Metric
In this metric as mentioned earlier in chapter 3, the next hop will be chosen only base on the DV. Therefore since the DV calculated and stored in DV_nodes array, the simulation can compare these numbers in this array, and selects the minimum value as the next hop. 220.127.116.11.
5.3.3 Regular Power aware DSAP Metric
In regular power aware DSAP metric, the DV will be divided by residual energy. Then the neighbor node with minimum value will be selected.
After calculating the DVs, then the same process will be performed to find the minimum value for final decision like as regular DSAP metric.
5.3.4 Proposed power aware DSAP Metric
To implement the proposed power aware DSAP metric, first the white-lie flag will be checked to find out, the neighbor node has been chosen before or not? If so, then the proposed metric will be calculated DV and the white-lie flag for that node will be reset. Otherwise, the DV will be calculated by the same metric of the regular power aware DSAP metric. 18.104.22.168.The white-lie flag will be set when the protocol selected a neighbor node as the next hop. 22.214.171.124. shown the code that the white-lie flag set.As the same as the regular power aware DSAP metrics simulation, the other procedures such as finding the neighbor nodes or finding the minimum DV value, are the same as the regular DSAP metric simulation.
CHAPTER 6 Result and analysis
In order to test the proposed metric, a simulation model of a stationary wireless sensor network included 12 nodes in 2D-4 nodes topology has been developed. From the simulation model, experiment has been carried out in order to obtain results. In the experiment, the source and destination are fixed which are Node 4 as source and Node 7 as destination (see 6.1).
As mentioned earlier in the previous chapter, there are some assumptions made for the simulation model. They are listed below:
* The network simulates without any Base station node, which means the packets route internally between a source node to a destination node.
* Nodes in network know about their location and their neighbors location.
* Each node knows about available energy of its neighbors.
* The energy consumes by processing does not considered. Only communication including transmission and receiving cost considered.
The simulation was ran with the initial energy 0.1 J for each node and it continued until the first node in the network died. 6.2 shows trend of energy depletion in node 5 which was the first node died in this network simulation. The energy needed to transmit and receive a message is shown below.
From the simulation model, k = 512, d = 15,
The value obtained from the formula is the amount of energy needed by the sensor nodes to transmit a message () and to receive a message (. These amounts of energies are consumed by the nodes involved in the path at every round of the simulation. Every time the node transmit or receive a message, the amount of energy shown in No.1 and No.2 will be deducted from the current amount of energy that the node has. From the simulation model, the 3 different versions of the DSAP have different amount of time for their first node to die as shown in 6.2. This is due to the different metrics used included the proposed metric.
As the graph shows in 6.2, all three metrics had the same dramatically decreasing trend until the round 2656 then the trend of the proposed power aware DSAP metric at the 0.06 level of energy is smoothly changed to up because of the routing protocol used some other path instead of involving the node 5 always in the path. Therefore the node 5 saved more energy for communication in the network.
As explained before in chapter 4 about the proposed power aware DSAP metric, the node's residual energy value will be divided by α to the purpose of representing untrue residual energy for the node. This causes to prevent of choosing the node 5 and involving the other nodes to the path. In addition, the proposed power aware DSAP metric makes this decision base on the number of node involvement on the path, which is, if the node has been taken one time before, then the new proposed metric will be chosen, otherwise, the regular power aware metric should be chosen.
Up to round 4426 the 2 original protocols had the same decreasing trend and then the regular power aware metric trend changed and continued with less degree until the node died, but the regular metric DSAP continued with straight trend until the node died. The trend of regular power aware metric changed because the metric looking for the most power node, therefore, after that particular level of energy, the regular power aware metric had chosen some other paths. Whereas, the regular metric DSAP always choose the shortest path, therefore the node 5 involved in path 100%.
From the experiment, it was found that first node died at round 8853 when the proposed power aware metric is used whereas, by using the regular metric, the first node died at round 6377. As for the regular power-aware metric the first node died at round 8361 (as shown in 6.3). By using the proposed power-aware metric, the network life time could be increased up to 16%.
The reason for the DSAP with the proposed metric to have longer lifetime is because of the factor that the neighbor node “lied” about the residual energy of the adjacent node which involved in the path. The proposed metric is mentioned in detail in chapter 4.
On the other hand, 6.4 shows the number of delivered message until the first node died. In this bar chart, it is obvious that the proposed power-aware metric increased the number of delivered messages compare to the other two metrics.
CHAPTER 7 Conclusion and future work
In recent years, many routing protocols have proposed for WSNs, and implemented with different applications. One of the necessaries in WSNs routing protocol that needs to be considered, is energy efficiency, because wireless sensor nodes have limited power in network, therefore routing protocol needs to more consider about node's energy conservation. Many researches have been done to develop power aware routing protocols for wireless sensor networks in recent years. One example of a power aware routing protocol is the Directional Source Aware Routing Protocol (DSAP) which was developed with some power aware metrics to prolonging the network lifetime.
Current power aware-DSAP metric most of the time takes the neighbor's node which has the most power with shortest path. Taking the particular paths causes to depleting energy in specific nodes in network and unbalanced power dissipation in network. Therefore, some nodes in the network stay untouched, whereas they could participate as a path to prolonging the network life time and also increasing the number of message delivery. If this problem is solved, the lifetime of the sensor nodes can be prolonged.
In this research dissertation, the metric proposed could help balancing the network's node energy dissipation by using different nodes properly as the chosen path instead of using some nodes more frequently.
According to the new proposed metric, when a node has been used one time before in path, it will take a new metric instead of using the current power aware-DSAP metric. Otherwise, it takes the power aware-DSAP metric and finds the node to route. When the new metric be chosen, the neighbor node will tell a lie about its remaining energy to its parent source node, then the new metric evaluate by this untrue energy value. It could decrease the chance of taking that node, which has been taken one time before. This new metric would call white-lie, because of the lie can help the network to be survive for more time. Hence, the network life time will be increase, and also other nodes will be use properly in path to increase the chance of message delivery.
Experiments shown that the proposed power aware metric increased the network lifetime about 16%, also the number of delivery messages increased too.
In conclusion, it can be said that, by using the proposed power aware metric for DSAP routing protocol, the network lifetime for a WSN can be increased. Therefore, the network can be survived more time to aggregate more data.
7.2 Future work
The proposed power aware metric for DSAP still has some areas to discover and do more research to improve its performance. The parameter α is a value to find the level of residual energy at node, however, the value α =1.5 is not the best value and needs more studying to find out an optimum formula to evaluate the best value for α.
Testing the proposed power aware metric, in large scale network with different sources and destinations, is one of the other interests that would be great to be tested. Also, different network topologies such as 2D-8 Nodes or even 3D topology needs to be explored in the future.
A.Salhieh, L. (2004). POWER-AWARE METRICS FOR WIRELESS SENSOR NETWORKS. International Journal of Computers and Applications .
Akayya, K., & Younis, M. (2003). Energy-Efficient Communication Protocol for Wireless Microsensor Networks. Elsevier .
Akkaya, K., & Younis, M. (2003). A survey on routing protocols for wireless sensor networks.
Ankit Mehta, D. T. (2005). Compendium of Applications For Wireless Sensor Network.
anmc.postech.ac.kr. (n.d.). Retrieved from http://anmc.postech.ac.kr
Deitel. (n.d.). C++ How to Program, Forth edition.
El-Haddad, S., Girod Genet, M., El-Hassan, B., & El-Nabbouch, D. (2008). MDSAP simulation using TinyOS and Hospital Application Modeling.
El-Haddad, S., Girod-Genet, M., & Hassan, B. E.-.. (2007). DSAP for wireless Sensor Networks- Modified. Algorithm and Simulation using OMNeT++.
I.F.Akyildiz, W. (2001). Wireless sensor networks : a surv