Main Page/Resources/E-motions/DSAPRealistic

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 Modeling Language (DSML), as well as its reliability in terms of energy efficiency. The longer the network lives, the more reliable its routing protocol. We show how implementing some variants of the protocol is trivial once the DSAP has been implemented. We also show how providing the protocols with more realistic behavior produce different results, which are more similar to those obtained in real life. We use e-Motions for the modeling and simulation. The implementation is realized for networks of any size and whose nodes can contain any number of 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 #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 the network of Figure 1.

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. They transmit 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-Based Engineering (MBE) approach and propose the specification of a Domain Specific Modeling Language (DSML) 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. Furthermore, we consider some realistic considerations that should be taken into account when developing compontent-based systems.

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. It consists of four non-abstract classes. WSN and Node classes allow to define the structure of a network, while RndmOb and RelOb classes are used to model how packets arrive and to keep track of the network reliability, respectively. The latter classes are created according to the Observers concept that we introduced in [4].

Figure 2 - WSN DSAP Metamodel


WSN class represents the network, and consequently incorporates the attributes to keep the previous information (engFor and engRec attributes), as well as the information with the initial nodes' energy (initEng), and attributes to indicate the number of nodes (nodes) and how many neighbors they have (nghbs, 8 in the network in Figure 1). The position of a node in the network is stored in the sequence edges of class Node, and target is a sequence containing the position of the target node(s) of the packets contained in a node. Other than these two attributes, Node objects have an id, their energy available (eng), the number of packets contained (pckts), the overall number of incoming and outgoing packets, and whether they have positive energy or not (alive). Node objects are linked to their neighbors by means of the nghbs relation. They also have information of the neighbors with positive energy (posNghbs relation). The former relation is important to know the topology of the network, while the latter allows knowing the neighbors a packet can be forwarded to.

There will be an object of type RelOb and another of type RndmOb in every network. The former captures the number of packets transmitted within the network (attribute incoming) and the number of those that reach their destination (attribute completed). It also contains two sequences, one (death) that registers the id of the nodes that run out of energy and the unit of time at which they do (time). RndmOb objects are used to randomly generate source and target destination nodes for packets.

Behavior

Here we define the generic behavior of the DSAP and its variants for n-neighbors WSNs. For now, 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 observer 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. In this specific example, such generator returns an Integer between 1 and the number of nodes in the network.

Image:CalculateRandom2.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. Finally, the attributes of the RndmOb are reseted for the next calculation of rule CalculateRandom.


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 n 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:PacketForwarding3.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..nghbs}.dv(n1.edges, n.target -> subSequence(1,nghbs)) / n1.eng <= Sequence{1..nghbs}.dv(i.edges, n.target -> subSequence(1,nghbs)) / 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..nghbs}.dv(n1.edges, n.target -> subSequence(1,nghbs)) / (n1.eng - n1.pckts*engFor) <= Sequence{1..nghbs).dv(i.edges, n.target -> subSequence(1,nghbs)) / (i.eng - i.pckts*engFor)).

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 with 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 could 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. Furthermore, in our specifications, there are many packets flowing within the network, and packets can arrive to random nodes with a random destination, whereas in related work [1] there is only one packet flowing within the network at all time.


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 (Power-DSAP for short) 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-DSAP v2.

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 chosen. 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-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.

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, so they prolong the node's lifetime as long as possible. In the Power-DSAP, the energy consumption is slightly more uniform than in the Power-DSAP v2, and the packets completed are 128, while in the latter protocol they are 123.

Figure 10 - Results with fixed arrivals

Realistic 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

For achieving such behavior, we have added two behavioral rules to our specification. Rule StandByConsumption (Figure 12) models the node energy consumption in stand-by: every node spends 2000 nJ every time unit simply for being alive. Rule RandomDeath (Figure 13) models random failures than can occur in nodes. It uses the concept of mean time to failure, which is the predicted elapsed time between inherent failures of a system or component during operation. Normally, these kinds of failures follow exponential distributions, so in our example it follows an exponential with mean 150 units of time (value obtained from the nodes’ manufacturer).

Figure 12 - Power consumption in stand-by

Figure 13 - Death due to random circumstances


The chart in Figure 14 shows the behavior of the Power-DSAP routing protocol in a network with 12 nodes and 4 neighbors, with and without these two additional rules. The chart displays, in both situations, the number of nodes alive at all times, and when they die. 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), and whether they have some energy when they die or not, indicated with a small drawing. In this particular situation, 83 packets reach their destination with the original Power-DSAP, while only 68 do in the realistic implementation – which also included the sudden death of a node (#2) at time 55. From that moment on, the remaining nodes have to do more work, and hence their energy is consumed faster. This is why the network only works until time 80, when only the nodes in the corners have some energy – but they cannot exchange packets. In the original implementation of Power-DSAP, energy in nodes is depleted from time 82 to 94, much later than in the realistic setting. This new model of the system also simulated more accurately the behavior of the real network when deployed.


Image:12nodesChart2.png

Figure 14 - A comparison between Power-DSAP and Power-DSAP with realistic behavior added


With these experiments we have shown that we are able to model and simulate real-life scenarios that were not considered in the related work that dealt with the DSAP.

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 projects and import them. There are two projects to download. They are contained in the DSAPPowerAwareV2.zip file and explained separately below.

WebSiteProject100Nodes

The project named WebSiteProject100Nodes contains the modeling and implementation of the Power-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-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.

Figure 15 - Simulating the WebSiteProject100Nodes project


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

WebSiteProject12NodesExtensions

The project named WebSiteProject12NodesExtensions contains two different implementations. The modeling of the Power-DSAP is located in folder Power-DSAP. Folder Power-DSAPExpDeath&SBConsumption contains the implementation of the Power-DSAP with the realistic rules to model power consumption in stand-by and random death in nodes. Both folders contain a readme.txt file where it is explained how to modify the example to get the variants of the DSAP.

Figure 16 shows a screenshot with the parameters to launch the simulation. An initial model does not have to be specified, since the network with 12 nodes is created with the Initial Rule.

Figure 16 - Simulating the WebSiteProject12NodesExtensions project


The simulation of this project takes up to 5 minutes.

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

4. J. Troya, A. Vallecillo, F. Durán, S. Zschaler. Model-Driven Performance Analysis of Rule-Based Domain Specific Visual Models. Information and Software Technology 55 (2013), pp. 88-110. DOI information: 10.1016/j.infsof.2012.07.009

Personal tools