Main Page/Resources/E-motions/DSAP

From Atenea

Jump to: navigation, search

Contents

Introduction

The work presented in this web page aims to model and monitor a protocol for WSNs named DSAP using a Domain Specific Visual Language (DSVL), as well as its reliability in terms of energy efficiency. The longer the network lives, the more reliable the protocol is. We show how implementing some variants of the protocol is trivial once the DSAP has been implemented. We use e-Motions for the modeling and simulation. The implementation is realized for networks where nodes have 8 neighbors.

Overview of the DSAP

The Directional Source Aware Routing Protocol (DSAP) was developed by Salhieh, Weinmann, Kochhal, and Schwiebert in 2001 [1]. It was designed for low-power fixed wireless topologies and based on local information where each node only knows about its neighbors information. It has several advantages over other routing protocols, including incorporating power considerations and having no routing table. Each node has a unique ID, which gives how far, in terms of number of nodes, the node is from the network perimeter in each direction. For example, the ID of the node numbered 43 in the WSN in Figure 1 is (3, 3, 4, 4, 6, 5, 5, 3). This means that there are three nodes (40, 41, 42) to the edge in direction 0 (left), three nodes (10, 21, 32) in direction 1 (up-left), four nodes (3, 13, 23, 33) in direction 2 (up), etc. Consequently, the ID is a vector with as many components as neighbors have the nodes in the network -- 8 in our case.

Figure 1 - Net with 100 nodes and 8 neighbours


When transmitting a packet, each node contains information about its neighbors' ID and the ID of the packet's target node. Each node transmits a packet to a neighbor which is closer to the destination. In order to choose which neighbor a packet is forwarded to, the Directional Value (DV) is used. The DV of each neighbor is calculated by taking their IDs and subtracting them from the destination node's ID. Let us imagine that node 22 wants to send a packet to node 77. The original DSAP protocol can be seen as a two-step routing protocol:

  • First, the source's and target's ID are subtracted. The result in our case is (2,2,2,2,7,7,7,2) - (7,7,7,2,2,2,2,2) = (-5,-5,-5,0,5,5,5,0). This obtained vector indicates which neighbors the packet can be forwarded to: those with a non-positive number are discarded. In this way, the packet will not be sent to nodes in directions 0 (left -- 21), 1 (up-left -- 11), 2 (up -- 12) and 3 (up-right -- 13).
  • The ID of those neighbors candidates to receive the packet is subtracted from the destination node's ID. The absolute values of the components in each resulting vector are added, which gives us the DV, and the neighbor with the smallest result is chosen. If there is more than one with the same value, one of them is randomly picked. In our case, DVs for the nodes numbered 23, 33, 32 and 31 are, respectively, 28, 26, 28 and 32. As it was obvious, the node 33 is closer to the destination and is the one chosen.


System Modeling

We present how to model the DSAP and some variants and their reliability metrics in terms of energy consumption. We follow a model-driven engineering (MDE) approach and propose the specification of a DSVL for the high-level modeling and analysis of the protocols, in terms of behavioral rules, in the design phases. We show how once we model the original DSAP, modeling each of its variants is trivial.

Structure

As in any Domain Specific Language (DSL), the structure of the system is given in terms of a metamodel. In Figure 2 we show the metamodel for representing networks in the DSAP context, and Figure 3 shows the metamodel for observers. These two metamodels are merged together in a non-intrusive way, so that non-functional properties of the DSAP can be modeled and monitored in the behavioral rules.

Figure 2 - WSN Metamodel


A WSN is composed of Nodes. Each Node has an identifier given by an integer (id -- 0, 1, 2 and so on). Another identifier, which gives the position of the node in the network according to what was explained in the Overview Section, is kept in the edges attribute, it is a sequence with 8 components in a 8-neighbors network. The remaining energy is kept in eng. The attribute named target contains the edges of the target(s) node(s) and pckts contains the number of packets that a node currently contains. These two attributes work like this: if there are no packets in a node, target is an empty sequence; if there is one packet, target contains a sequence with 8 components (in a 8-neighbors network); if there are more than one packet, target contains a vector with 8*pckts components, where the first 8 components represent the edges of the target node of the packet that arrived first, and so on. Attributes incoming and outgoing contain the total number of incoming and outgoing packets in the node, and alive is a boolean stating if the energy of the node is above 0 (alive=true) or not (alive=false). If a node is not alive, it can neither receive messages nor forward them. As for the references, every node has a link (nghbs) to each neighbor and another link only to the neighbors which are alive (posNghbs).

Figure 3 - Observers Metamodel


There are two observers, named RelOb and RndmOb. The former is to be keeping the number of packets that arrive to the network (incoming) and those that reach their target node (completed). It also contains two sequences, death and time, that are to store the identifier of the nodes which die and the time they die. The latter observer is used to randomly select nodes from and to which packets are sent.

Behavior

Here we define the behavior of the DSAP and its variants for 8-neighbors WSNs as that presented in Figure 1. We want to carry out two different analysis, one to study the overall network behavior and another one for a more specific and local study. In the former, packets arrive at nodes randomly picked and their target node is also random. In the latter, packets are always sent from node 22 to node 77 (for the network in Figure 1).

To take into account the energy of the nodes and the size of the packets, we use a simple radio model described in [2]. To simplify the explanation, every node dissipates 25612.8 nJ in the transmission of a packet and 25600 nJ in its reception. We suppose that every packet starts with an energy of 1000000 nJ. Our initial model is the network composed of 100 nodes shown in Figure 1. There are also a RelOb and a RndmOb observers.

Rules CalculateRandom and PacketArrival deal with the arrival of packets to the network. The former is shown in Figure 4, and the latter in Figure 5. Rule CalculateRandom assigns the identifier of two nodes to the attributes of RndmOb whenever the value of such attributes is -1. Such identifiers must be different and both nodes must be alive. There are two variables in the rule which use the random generator provided in e-Motions.

Image:CalculateRandom.png

Figure 4 - CalculateRandom Rule


Rule PacketArrival introduces the packet in the node assigned in rule CalculateRandom. It updates its corresponding attributes and it also updates the incoming attribute of the RelOb observer with the arrival of the new packet.

Image:PacketArrival.png

Figure 5 - PacketArrival Rule

Rule PacketForwarding (Figure 6) models the forwarding of a packet to the alive neighbor with the lowest DV. The OCL condition in the LHS checks that node n0 has a packet to forward and n1 is a neighbor with positive energy and the lowest DV. That expression uses a helper, named dv, which deals with the calculation of the directional value and is: context Sequence::dv(s1 : Sequence, s2 : Sequence): Integer body: self -> iterate(i ; acc : Sequence = Sequence{} | acc->append(i.abs())). In the rule's RHS, the attributes of the nodes are modified with the updating of the energy, the number of packets contained, incoming and outgoing packets, etc. The RelOb observer updates its completed attribute when n1 is the target node of the packet being forwarded.


Image:PacketForwarding.png

Figure 6 - PacketForwarding Rule


To model some of the variants of the DSAP, we only need to change the OCL condition of the PacketForwarding rule's LHS. For example, we can model the Power-DSAP with power-aware routing [1]. It selects the paths according to the ratio of the directional value and the power available at the neighboring nodes. The OCL condition would be this: n.pckts > 0 and n.posNghbs -> forAll(i | Sequence{1,2,3,4,5,6,7,8}.dv(n1.edges, n.target -> subSequence(1,8)) / n1.eng <= Sequence{1,2,3,4,5,6,7,8}.dv(i.edges, n.target -> subSequence(1,8)) / i.eng). We have developed another variant, where the routing selects the path according to the ratio of the DV, the power remaining at the neighboring nodes and it also takes into account the packets contained at the neighboring nodes and the power they will spend in forwarding them. The OCL condition of the PacketForwarding rule's LHS would be the following: n.pckts > 0 and n.posNghbs -> forAll(i | Sequence{1,2,3,4,5,6,7,8}.dv(n1.edges, n.target -> subSequence(1,8)) / (n1.eng - n1.pckts*25612.8) <= Sequence{1,2,3,4,5,6,7,8}.dv(i.edges, n.target -> subSequence(1,8)) / (i.eng - i.pckts*25612.8)).

Finally, there are two rules which model the energy consumption in nodes. They are NegativeEng (Figure 7) and UpdatePosNghbs (Figure 8). The former is fired whenever a node which was active runs out of energy. The RelOb observer updates its time and death attributes with the time the node died and its identifier. The alive attribute of the node turns to false.

Image:NegativeEng.png

Figure 7 - NegativeEng Rule


The UpdatePosNghbs is fired when a node dies. It is fired for each ocurrence of a posNghbs link going from a node to the death node and it removes such link. Thus, this rule aims at removing all the posNghbs incoming links to the death node, which avoids sending packets to that node according to the PacketForwarding rule.

Image:UpdatePosNghbs.png

Figure 8 - UpdatePosNghbs Rule


Regarding the rules' duration, notice that we have established that a new packet arrives every time unit and nodes forward a packet (as long as they have any) every time unit too. Rules that model the death of a node or that choose the incoming and target nodes for a packet are instantaneous rules. To make the model more realistic, rules that model the packets arrival and forwarding should follow some probabilistic distributions, something that we are able to model as we already presented in [3]. However, to make the simulations the least random possible, we decided to set these times as 1 in order to compare the different protocols in the different simulations in a fair way.


Reliability Analysis with a 100-nodes and 8-neighbors network

We want to carry out two different analysis. In one of them, the source and target nodes of packets are chosen randomly, while in the other packets always go from node 22 to node 77 (Figure 1). The first one models more accurately the reality, while the second one allows us to study the protocol locally to nodes 22 and 77. For both kinds of analysis, we have run three protocols: (1) the original DSAP protocol, (2) the power-aware DSAP and (3) a new protocol that also takes into account the packets that still need to be processed in each node apart from the remaining energy. Let us call the last one power-aware DSAP v2. In the three protocols we consider all the neighboring nodes as candidates nodes to forward a packet and not only those whose substraction with the target node is positive.

Random Arrivals

In these simulations, the RndmOb observer deals with the random selection of the source and target nodes for every packet. Packets are forwarded uniformly: every time unit a new packet arrives to the net and also every time unit every node which contains at least one packet forwards the packet that arrived first to a neighboring node according to the routing protocol being applied. We are interested in knowing the lifetime of the network in each protocol. For that, we will consider that the network dies when a node consumes all its energy. So we will measure the reliability in terms of the time the network has been alive and the number of packets completed (those that reached their destination) within that time.

As we can see in the simulation results shown in Figure 9, the power-aware DSAP is more reliable than the original DSAP. Besides, it turns out that it is also more efficient than the new developed protocol that also takes into account the packets that still need to be processed in the nodes.

Image:resultsDSAP1.png

Figure 9 - Results with random arrivals

Fixed Arrivals

We have made these simulations stop when all the energy in the nodes around 22 or 77 is consumed, so that no packet can reach its destination (77). We have made node 22 not to consume any energy when forwarding packets and node 77 when it receives packets. Otherwise, the energy in these nodes would be consumed soon.

In Figure 10 we can see the time at which the energy in each of the nodes around node 22 is consumed for each protocol. Let us focus first in the original DSAP. Since it does no take into account the remaining energy in the nodes, it always follows the shortest path to the destination. This is why it always uses node 33 from 22 to send packets to node 77 at the beginning. This makes the energy in node 33 to be consumed quickly, in time 22. Then, the protocol forwards packets to nodes 23 and 32 from 22 because they are at the same distance from the destination. The energy at both nodes is consumed almost at the same time, at times 61 and 63, respectively. The same happens then with nodes 13 and 31 and later with nodes 12 and 21. The last node to run out of energy is the 11. The number of packets that reach node 77 are 87.

In the other two protocols, the energy consumption in the nodes is much more uniform, since they take into account the remaining energy at nodes. In the power-aware DSAP, the energy consumption is slightly more uniform than in the power-aware DSAP v2, and the packets completed are 128, while in the latter protocol they are 123.

Image:resultsDSAP2.png

Figure 10 - Results with fixed arrivals

Reliability Analysis with a 12-nodes and 4-neighbors network

Here we show experiments with the 12-nodes and 4-neighbors network shown in Figure 11. These experiments are more realistic since we consider power consumption of nodes in stand-by and failure of nodes due to other circumstances apart from energy depletion. In fact, WSNs can be deployed in many and different environments, so there are different causes that can make nodes die. For example, animals could try to eat them, or they could be damaged due to environmental conditions.

Figure 11 - 12 nodes WSN net

The chart in Figure 14 displays three different executions in such network:

  • The blue one (Power-DSAP) is an execution with the Power-DSAP. Recall that every node dissipates 25612.8 nJ in the transmission of a packet and 25600 nJ in its reception.
  • The red one (Power-DSAP SB consumption) uses the Power-DSAP and it also considers the power consumption of nodes in stand-by. Concretely, every node consumes 3000 nJ every unit of time. The rule used to model this is the simple one shown in Figure 12.

Image:EngConsmp.png

Figure 12 - Power consumption in stand-by

  • The green one (Power-DSAP exp death) applies the Power-DSAP and it also considers the failure in nodes due to other circumstances than the energy depletion. Such failure follows an exponential distribution of mean 200 units of time. To model such failure, the rule shown in Fig. 13 has been used. Note that the RelOb observer has a new attribute, eng. It is of type Sequence and we use it to store the remaining energy in nodes when they die.

Image:ExpDeath.png

Figure 13 - Death due to random circumstances

The X axis of the chart shows the simulation time, while the Y axis indicates the number of nodes alive. It can be seen as well the concrete nodes that die (indicated by the numbers on the lines). In the case of the Power-DSAP exp death, it is indicated between brackets the energy available in the nodes when they die. In the three cases, packets arrive at random nodes, and their destination is also random. Let us analyze each of the three cases.


Image:12nodesChart.png

Figure 14 - Death of nodes along time


In the Power-DSAP, the first node (number 4) dies due to energy depletion in time 82. From that moment, several nodes die, until node number 6 does in time 98. From that moment, the nodes alive are 0, 3, 8 and 11, which cannot exchange packets among them, so there is not packet flow any longer. That is the reason why no more nodes die from time 98. The number of packets that arrive to their destination is 83.

In the Power-DSAP with power consumption of nodes in stand-by, the first node (number 9) dies due to energy depletion in time 71. It happens earlier in simulation time than in the previous case due to energy consumption in stand-by. From that moment, several nodes (10, 7, 2, 6, 1 and 4) run out of energy until time 82. At that point, only nodes 0, 3, 5, 8 and 11 are alive. They cannot exchange packets between them because they are not directly connected. This is why they die later in time: the remaining energy in those nodes from unit of time 82 is depleted only due to power consumption in stand-by, being no packet flow any longer. The last node to die is number 11 in time 146. 75 packets arrive to their destination in this case.

In the Power-DSAP that considers the death of nodes due to other circumstances apart from energy depletion, the first node (number 3) dies in time 8. When it dies, its energy is 948787.2 nJ, so it dies due to a random circumstance. The same happens with nodes 0 and 8, which also die quite early in time. Having three nodes less already in time 53, the remaining nodes have to work more. This causes the energy of node 6 to be depleted in time 55, and the energy in nodes 1, 5, 10 and 11 to be depleted in times 59, 60, 64 and 65, respectively. From unit of time 65, the only nodes alive are 2, 4, 7 and 9. Their energy is not consumed anymore since they cannot exchange packets, so all of them die due to other circumstances. The last one to do it, is node 9 in time 493. The number of packets that arrive to their destination is 51.

With these experiments we have shown that we are able to model and simulate real-life scenarios that were not considered in the papers that dealt with the DSAP. The values chosen for quantity of energy consumption per time unit and the distribution followed for the failure of nodes due to random circumstances could have been different depending on the network. In any case, our experiments serve as proof of concept for our approach.

Simulation

In order to run the simulations, first the e-Motions tool has to be downloaded. It can be done from here. Then, create a new eclipse workspace. Once inside the workspace, Maude has to be configured, as explained here.

The next step is to download the project and import them. It is contained in the DSAPPowerAwareV2.zip file and explained below.

The project is named WebSiteProject100Nodes and contains the modeling and implementation of the Power-aware DSAP v2 with an initial network with 100 nodes. It contains a readme.txt file where it is explained how to modify the example to get the original DSAP and the power-aware DSAP.

Figure 15 shows a screenshot with the parameters to launch the simulation. The initial model with the 100-nodes network is kept in the DSAP100.xmi file, so it has to be set in the configuration window.

Image:sim100-4.png

Figure 15 - Simulating the WebSiteProject100Nodes project


Please take into account that the simulation of this project lasts for several hours.


References

1. A. Salhieh, J. Weinmann, M.Kochhal and L. Schwiebert. Power Efficient Topologies for Wireless Sensor Networks. International Conference on Parallel Processing, pages 156-163, 2001.

2. K. Jalil and M. Nategh. A Composed Energy Aware Metric for WSNs. In ICCDA'10, Volume 2, june 2010.

3. J. Troya and A. Vallecillo. A Domain-Specific Language to Specify and Simulate Queuing Network Models. Submitted, 2012

Personal tools