Journal of Global Research in Computer Sciences
MenuISSN: 2229-371X
ISSN: 2229-371X
S. Geetha Priya1, A.R. Arunachalam2
|
| Corresponding Author: S. Geetha Priya, E-mail: sgpriya15@gmail.com |
| Related article at Pubmed, Scholar Google |
Visit for more related articles at Journal of Global Research in Computer Sciences
This paper deals with a novel forwarding scheme for wireless sensor networks aimed at combining low computational complexity and high performance in terms of energy efficiency and reliability. This paper analyses the disadvantages of excessive clustering time because of the possible uneven cluster density. As a result, we present an ASMC algorithm. The proposed algorithm provides adaptability to mobile nodes and has no limitation to the network extensibility. An analytical model for estimating the energy efficiency of the scheme is presented, and several practical issues such as the effect of unreliable channels, topology changes, and MAC overhead are discussed.
KeyTerms |
| ASMC, energy efficiency, packet splitting, reliability, wireless sensor networks. |
INTRODUCTION |
| A wireless sensor network is a collection of sensor nodes organized into a cooperative networks. A sensor is a small device which observes the environment of physical parameters such as temperature, pressure, relative humidity, sound, vibration, motion or pollutants, at different locations. Wireless Sensor Networks (WSN) is highly distributed networks of wireless sensor nodes, deployed in large numbers to monitor the environment or system. Sensor nodes have limited transmission ranges and organize themselves in an ad hoc manner, which means that two wireless sensor nodes that cannot reach each other directly transmit on other sensor nodes to relay data between them .In general ,data packets from the source node have to traverse multiple hops before they reach the destination.In recent years, in order to guarantee the WSNs survivability and increase the network lifetime in such special-purpose environments, various energy-efficient schemes have been proposed in the literature [1-5]. Many algorithms mainly focus on the energy balance of the nodes to prolong the lifetime. Clustering is one of the basic approaches for designing energy-efficient, robust and highly scalable distributed sensor networks. A sensor network reduces the communication overhead by clustering, and also decreases the energy consumption and the interference among the sensor nodes. |
METHODOLOGY |
| A .Minimizing the energy consumption |
| The aim of reducing energy consumption while taking the algorithmic complexity into account, proposed a novel approach that burst the original messages into several packets, such that each node in the network will forward only small sub packets. The splitting procedure is achieved applying the ASMC algorithm. The sink node, once all sub packets (called splitting components) are received correctly, will recombine them, thus reconstructing the original message. The splitting procedure is especially helpful for those forwarding nodes that are more solicited than others due to their position inside the network. The proposed approach, almost all nodes operate as in a classical forwarding algorithm and, with the exception of the sink, a few low-complex arithmetic operations are needed. The sink node is computationally and energetically more equipped than the other sensor nodes, the overall complexity remains low and suitable for a WSN. Moreover, the proposed technique does not require the use of disjoint paths. Some preliminary results of this approach have been presented but they were empirical only and obtained through simulations on a sensor network where it is assumed that an ideal communication among neighbor sensors occurs, and all the burst components can be received correctly between a pair of nodes. |
| Through analytical model allows us to derive accurate results regarding energy consumption and complexity. The effect of important parameters such as nodes density and transmission range through both extensive simulations and an analytical study of the tradeoff between energy saving, complexity, and reliability of the proposed technique. In WSN, data generated by each node, are to travel from multiple sources to a data recipient or sink rather the communication between nodes. |
| B. Forwarding Technique |
| A sensor network where sensor nodes periodically send messages to a sink node through a multi hop transmission. The basic idea is to burst the messages sent by the source nodes so that a reduced number of bits are transmitted by each forwarder node. In order to better understand the main idea, the example in Figure 1. Nodes A and B have to forward a packet to the sink S and can do it through nodes X, Y, and Z, which are all in the coverage range of A and B. If a normal forwarding scheme is adopted, two cases, Case a) A and B select different next-hop nodes .This happens with probability 2\3. Case b) A and B select the same nexthop node. This happens with probability 1\3. |
| If there are ω bits for each packet, the maximum numbers of bits transmitted by a node belonging to the set {X, Y, Z} is w bits in the case a) and 2ω bits in the case b). Let now assume that each node in the set {X, Y, Z} knows that A and B have three possible next-hops and that a different forwarding scheme is adopted, as shown in Figure 1. In particular, when X, Y, and Z receive a packet, they split it and send to the sink only a part. In this case, X, Y, and Z have to transmit at most bits each. While comparing the two forwarding methods, its concluded that the last one reduces the maximum number of bits transmitted by a node belonging to the set {X, Y, Z} .More precisely, the reduction factor is 1-2\3=1\3. When comparing the bursting procedure with the procedure shown in case a), and (2- 2\3).1\2 = 2\3 when the bursting procedure is compared to the procedure shown in case b). Summarizing, an average reduction factor of 4/9 is obtained. Accordingly, the lifetime of a sensor network increases as the energy consumption is more distributed among the nodes. It is worth remarking that the bursting procedure has to be performed in a simple manner, and consequently with low energy consumption. |
 |
| The total amount of transmitted bits does not change (bits are transmitted anyway, either with or without splitting); by bursting of packets it is possible to reduce the maximum number of transmitted bits per node and therefore the mean energy that each node consumes for the transmission.. Finally, it can be observed that if a perfect balancing is possible, which occurs when the number of next-hop nodes is a factor of the number of transmitted messages (i.e., the number of messages is exactly divisible by the number of next-hops), the energy consumed by nodes will be the same either with or without bursting. However, if this is not the case, using a bursting technique makes the number of forwarded bits significantly reduced. Moreover, the reduction increases if the ratio “message length over number of components “decreases. |
ADAPTIVE SPLIT-AND-MERGE CLUSTERING ALGORITHM |
| Generally, when the network has appropriate cluster density and the nodes adopt appropriate power control algorithm, the sense delay will only be constrained. However, sometimes cluster head will accept a large amount of nodes as its cluster members. In fact, the nodes during clustering are among the state of sensing, receiving or sending other than sleeping. The prolonging clustering time certainly will consume more energy and shorten the network lifetime. Actually, cluster density exerts an influence on the duration of many clustering tasks, such as calculating, sending, and receiving the list of timeslots. Usually, high cluster density brings about its negative effect by extending the running time of many tasks, such as time synchronization, node location, key distribution and so forth. As these tasks also take up clustering time, high cluster density will markedly prolong clustering time which has significant influence over the nodes sleeping time that dominates the whole network remaining energy. Taking into account all these factors, we present ASMC algorithm. The bellow algorithm 1 is the proposed ASMC algorithm description. Algorithms 2, 3, 4 describe three main procedures in ASMC algorithm, namely, split, mergence and cluster head by-election, respectively. |
| Definitions: |
| MRENID: Maximal Remaining Energy NodeID |
| Aj : a set of cluster heads whose number of cluster entry is greater than Q1 |
| Bj: a set of cluster heads whose number of cluster entry is less than Q2 |
| Algorithm 1: |
| Preset cluster heads number in first round according to the expression: N/k; |
| foreach cluster head j do |
| Broadcast Cluster_Head_Msg (MREICNID); |
| Accept the joining nodes |
| foreach cluster head j ∈ Aj do Split; //see algorithm 2. foreach cluster head j j ∈ Bj do Merge; //see algorithm 3. |
| Collect MRENID and MRENA; |
| Launch cluster heads by-election when the cluster heads identity broadcast received is less than N/k; // see algorithm 4. |
| end |
| Algorithm 2: |
| foreach cluster head j ∈ Aj do |
| Cease to accept the joining nodes; |
| Designate a new cluster head; |
| end |
| Algorithm 3: |
| foreach cluster head j ∈ Bj do MREICNID=NULL; end |
| Algorithm 4: |
| foreach cluster head j ∈ C j do Designate a new cluster head; end |
METRICES FOR ENERGY EFFICIENCY |
| In particular, for comparison purposes, the Shortest Path with Load Balancing (SP) is considered. The SP approach is very similar to the probabilistic routing. A sensor node having a packet to forward choose randomly as relayers a neighbor node toward the sink so that the number of hops needed to reach the sink is minimized. Load balancing (i.e., a random choice of the relayer) allows prolonging the network lifetime, avoiding that some nodes could be overloaded. Throughout, considered that an SP packet is composed by K words of ω bits each and that the burst-based splitting procedure can be applied to each word by considering that the same is used for all the words of same packet. The overhead due to the MAC layer head, but it is worth noting that all the words in the packet generated by the splitting procedure are represented with the same number of bits and therefore their length can be obtained from the prime number used to split the packet. With the above hypothesis, the expected energy reduction factor can be expressed by considering mean energy consumed by a node in the case of the proposed burst-based and the SP forwarding technique respectively, where and are the mean number of forwarded packets with the above forwarding schemes, is the mean number of bits needed to represent the burst components, and is the energy needed to transmit a bit. |
| However, if a large number of packets are considered, the expected total number of bits is .In several papers about WSNs, the network lifetime is related to the time until the death of the first node. In this case, the maximum energy consumed by a node should be also considered. Therefore, in this project it investigates also the energy reduction factor related to the maximum energies where and are the maximum number of forwarded packets. Obviously, the set o of primes should be properly chosen in order to maximize the above matrices. |
ENERGY REDUCTION FACTOR |
| It is important to observe that the set of prime numbers with can be arbitrarily chosen provided that. Therefore, the number of bits needed to represent can be reduced by choosing the prime numbers as small as possible. As a consequence of this choice, the MERF is maximized. Throughout, it indicates with Minimum Primes Set (MPS) the set of the smallest consecutive primes that satisfy the condition. For instance, if and is a 40-bit word, the MPS will be (this is the set of smallest four consecutive primes that satisfies the condition). The MERF in this case is 0.725. However, when the primes set are chosen as above, the message can be reconstructed if and only if all the burst components are correctly received by the sink. Let’s consider another primes set. |
| The choice it is possible to reconstruct the original message even if component is lost (i.e., if we have one failure). In fact, whatever the lost component is, the product of the primes associated with the received components satisfies the condition, and therefore it respects the hypothesis of the burst theorem. For instance, if the last component is not received, it is again possible to obtain as, where is the product of the first three primes, and the first three burst coefficients computed for the MPS-1. |
| 1. The number of components is not changed (i.e., the same number of forwarders is needed). 2. The MERF obtained with the new set is 0.65, i.e., MERF is reduced by about 11%. |
| Because usually sensor nodes have simple processing units, it is mandatory to have a low complex procedure for obtaining values. This goal can be easily reached if is fixed or takes only a few values. This is a very fast procedure. |
SYSTEM IMPLEMENTATION |
FORWARDING ALGORITHM |
| The forwarding algorithm is based on two temporal phases, the Initialization phase and the Forwarding phase. The initialization phase is to split data’s and the forwarding phase performs forwarding. |
INITIALIZATION PHASE |
| This phase organizes the network in clusters and also has the advantage of minimizing the number of hops needed to reach the sink .The Initialization phase has been described in detail and it is realized through an exchange of initialization messages (IMs) starting from the sink that is supposed to belong to the cluster. Retransmit the IM. On the basis of the received IMs, at the end of the procedure each node in the network will know its own next-hops, which other nodes will use it as a next-hop, and into how many parts the received packets. |
 |
| The sink sends the first IM for the initialization phase each node can obtain the MPS and select a different prime number of the MPS-f by considering the order of the addresses specified in the IM. Recall that in order to obtain the MPS- f, it is sufficient to know to be either fixed or specified within the IMs, while the number of primes corresponds to the number of possible next-hops (that each forwarding node knows on the basis of the received IMs) Because could be different for each source node , it use the notation . |
| However, the sink, in order to reconstruct the messages, also needs to know the index of the received component (i.e., for each). For this purpose, it will assume that in the header of each packet there is a field called mask. The mask could be the binary representation of the index followed by the number of components [i.e., pair] or a “one-hot” coding bit sequence followed by a tail bit .Its assumed that the overhead introduced by the mask is negligible. According to the previous initialization procedure shown in Figure .It will receive the IM with from the node X, and it decides to belong to, node Y will have only one next-hop (i.e., X) because Y is at the end of the coverage range of nodes belonging to. Now, we consider what happens with the modified procedure. |
 |
| The proposed initialization procedure can be further refined in order to increase in some cases the number of possible next hops that a node can use as forwarders. In particular, when a node receives very few IMs with, it does not choose immediately to belong to the cluster, but it waits for the IMs with the next sequence number in order to belong to the last cluster if it is more convenient. |
| When node Y receives the IM with, it postpones its decision to belong to other node. After some time, it will receive two new IMs with from nodes A and B, and therefore it decides to belong to in order to have two possible next-hops instead of one as shown in Figure 3. Basically, that anode can postpone its decision to belong to a particular cluster if the number of IMs received is less than a chosen threshold, but this can be done just one time in order to avoid an increase of the number of hops needed to reach the sink. The threshold can be a constant value (either specified in the IM or pre stored in the node memory, and therefore already known by the node). Moreover, if the number of received IM is less than the threshold, it is possible to use the conventional shortest path approach (SP) that keeps working also with our technique. The initialization procedure is performed only when the network is activated for the first time, and it is not necessary to run it when either a new node joins the network or a node runs out of energy. In both cases, it is sufficient that few IMs are exchanged between the node and its neighbors belonging to the near clusters. More details about the operations needed for the above cases have been described. Moreover, in order to consider the unreliability of the channel, which causes loss of IM packets and consequently nodes with an in sufficient number of neighbors, each node can start periodically a new joining procedure. |
| C. FORWARDING PHASE |
| Once the network has been organized, the Forwarding phase is applied. Basically; all nodes follow the same forwarding rule: If there is a number of neighbors at least equal to, and the packet has not previously split, then split the packet; else use conventional shortest path approach. Let’s consider the network shown, where clusters are obtained according to the initialization procedure already described in the previous section. The messages sent by each node when the source node H sends a message to the sink S. According to the initialization procedure, node G knows that it is the only next-hop of node H, and therefore it must forward the packet without performing a splitting procedure. It is worth highlighting that it is not necessary for G to specify the list of the destination addresses in the packet. In fact, in the initialization phase, nodes have already received the IM message, and therefore they know that node G has four next-hops and that all of them have to split the messages received from G into NG=4 parts. Therefore, when they receive the packet, according to both the packet size and they independently select the prime numbers 3 and send the components, together with a proper mask, to one of the possible next-hops. When the sink receives a component, it identifies the number of expected components on the basis of the mask, and therefore it calculates the MPS-f and the coefficients needed to reconstruct the original message. |
| Concerning the complexity of the algorithm, it is worth mentioning that the message splitting is performed only one time by the nodes that are the closest to the source and have the opportunity to do it (e.g., if they are in proximity of a number of neighbors higher than the threshold specified for the initialization phase), whereas the other sensor nodes in the network will just forward the sub packets. Moreover, only the sink node will reconstruct the original message through more complex operations as described, but this can be consider that usually the sink node is computationally and energetically more equipped than the other sensor nodes. Obviously, in the case of very large packets, it is possible to split the packets recursively, but in order to keep the complexity of the proposed algorithm very low ,its consider that a packet can be split only one time. |
PERFORMANCE EVALUATION |
| In this section, the comparison of the performance of BURST in terms of energy consumption to those obtained by SP. Moreover, provided some results obtained comparing the BURST to the most naive splitting scheme, a simple packet division into chunks. |
| The results have been obtained through a custom MATLAB simulator. A comparison between the results obtained through the analysis and those obtained through the simulator. Then, we analyze some other parameters in order to show the advantages of the proposed technique. |
 |
| Figure 5 shows the values of transmission 1 and transmission 2 are taken by simulating the packet forwarding Let consider a sensor network where nodes are randomly distributed in a square area of size m, with density nodes/m . Sensor nodes are assumed to be static as usual in most application. |
 |
| Figure.5, shows the values of transmission 1 and transmission 2 are taken by simulating the packet forwarding In each simulation, the sink node is located in the centre of the square grid, and each sensor node has a transmission range equal to m. |
CONCLUSION |
| A novel forwarding technique for wireless sensor networks based on the ASMC algorithm is able to predict the energy efficiency of the process. The choice of the clustering algorithm parameters in order to keep the processing complexity low, and then the tradeoff between energy consumption and reliability are measurable. Finally, the overhead introduced in terms of packet header size in MAC layer will be reduced. Simulation results have confirmed the results obtained and have shown that applying the ASMC-based technique significantly reduces the energy consumed for each burst node, reduces computational complexity and consequently increases the network lifetime. |
References |
|