The Validation of Global Minima Scheme in Wireless Sensor Networks

The Validation of Global Minima Scheme in Wireless Sensor Networks

Mahima Mehta, Kaushik Ghosh

Department of Computer Science and Engineering College of Engineering and Technology, Mody University Lakshmangarh, India

AbstractThis paper considers the Global Minima Scheme in Wireless Sensor Networks and its validation using MATLAB. The Global Minima Scheme is used to deliver messages of interest to multiple sink nodes within different geographic target regions. In the existing Minima algorithm, Greedy forwarding is used along with the concept of Fermat point. Although the Global Minima Scheme is already proposed for efficient delivery of packets to multiple sink nodes, this paper will validate the Global Minima Scheme using MATLAB due to the fact that a cross verification of an algorithm is needed before it could be used for practical applications. Here we have approached by considering one function at a time and finally clubbing them together at the end. MATLAB has been used for validating because of its visualization effects that helps to analyze the transmission procedure.

KeywordsWireless Sensor Networks; Fermat Point; Minima method; Greedy forwarding; Grid deployment; Geocasting.

1. INTRODUCTION

   Sensor Networks are used extensively in mobile and wireless communication. In particular Wireless Sensor Networks has been a prominent topic of research in the present and last decade. A Wireless Sensor Network consists of spatial deployment of independent sensor nodes to monitor environmental and physical conditions and cooperatively transmit their data in the form of packets through the network to single or multiple sink nodes within different geographic target regions. There have been many routing protocols that have been proposed for transmission of messages from source to multiple sink nodes. In this paper, the existing Minima Protocol [1] is taken into consideration for the transmission of packets. The Global Minima scheme was designed to send same messages to multiple sink nodes in different geocast regions in a wireless network. This protocol uses a tree-like structure in order to transmit the packets from a source node to multiple sink nodes via a shared path. The Global Minima Scheme for packet transmission is based on the geometrical concept of Fermat Point [2]. In order to address the presence of multiple target nodes, the authors in [3] have considered a geometry driven scheme. The concept of Fermat Point [4, 5] was used to reduce the network traffic and packet delivery latency by optimizing the total path travelled by the packet to reach the destination nodes. The Fermat Point is a point within a polygon such that the sum of distances from that point to all the vertices of the polygon is minimum, as shown in Fig. 1.

   Fig. 1 Fermat Point for a polygon.

   The major issues in transmission of packets in a WSN are power consumption and delay incurred in the delivery of the packets. Both the issues are related to the distance travelled by the packet and hence can be solved by using the concept of Fermat Point. The Global Minima scheme discussed in [1] ensures that packet travels minimum distance, in order to consume minimum energy and produce minimum delay in the delivery of the packet. The Friis free space equation suggests

   (1)

   where Pr, Pt, Gr and Gt are the power consumed for reception and transmission and gains of receiving and transmitting antennas respectively. Hence, the Power is saved if the total distance travelled by the packet is reduced.

   This paper deals with the validation of the Global Minima Scheme using MATLAB. MATLAB is a high level language of technical computing and has an interactive and user- friendly environment. There are numerous mathematical functionalities, layouts and visualization effects in MATLAB which helps the users with Numeric computations, data analysis and visualization. MATLAB is used specifically for validation of the Minima protocol because it provides better visualization of deployment of sensor nodes and henceforth helps in the understanding of the packet transmission using the concept of Fermat Point.

   In Section 2 of this paper, different Fermat Point based routing protocols are discussed followed by discussion on the Global Minima Scheme and Packet Forwarding techniques in Section 3 and Section 4 respectively. In Section 5 the validation of the Minima Method using MATLAB is discussed. The functions that are taken into consideration for

   this paper deals with the calculation of Fermat Point and hence finds the Fermat Node for delivering packets. After the Fermat Node is found, the path followed by the packet to reach the Fermat Node from the source is validated. Along with this, the transmission paths followed by the packet from Fermat Node to multiple sink nodes is also validated using MATLAB in Section 5 followed by conclusion in Section 6.

2. RELATED WORKS

   1. The Geometry Driven Scheme

      The Geometry Driven Scheme for packet transmission was given for multiple geocast regions. In [3] the authors have discussed the Geometry Driven Scheme, wherein there are two geocast regions (B and C) and a source (A), each representing the three vertices of a triangle ABC, as shown in Fig. 2(a). The Fermat Point P of the triangle ABC hence formed is calculated based on the minimum summation of the distances from Fermat Point to all the vertices of the triangle. This scheme is very efficient for two geocast regions. But the limitation of this scheme is that as the number of geocast regions increases and exceeds two, a heuristic approach is followed for the calculation of Fermat Point of the polygon. The heuristic approach however fails to locate the exact Fermat point when the number of target regions are more than two. Infact, more the number of target regions beyond two, more is the factor of error added in calculation of fermat point. Moreover if any of the angles of the polygon exceeds 120 then the concept of Fermat Point does not hold good.

      Fig. 2 (a) Geocast Driven Scheme for two Geocast regions.

      As stated earlier, the Geometry Driven Scheme was extended for packet transmission from source to more than two geocast regions.

      As in Fig. 2(b), first any two geocast regions are considered and their Fermat Point F1 is calculated. Then considering another triangle with F1 as one of the vertices of the triangle, source as another and the third geocast region as yet another vertex of the triangle, the Fermat Point F2 is calculated. This point F2 is considered as the final Fermat Point for these three geocast regions. For more geocast regions, the same procedure is followed as discussed in [3].

   2. Lifetime Enhancement of Multi-Sink Wireless Network using Data Aggregation

      The authors in [6] have discussed another importance of packet forwarding using the concept of Fermat Point. Data aggregation is another way to enhance the lifetime of Wireless Sensor Network through reduction in energy expenditure during the transmission of the packets. A novel scheme was proposed to reduce the total number of transmissions by data aggregation. In [6] the authors have divided the transmission of packets into two phases wherein the first phase is routing the packets from the source to the Fermat Node and the second phase included the final transmission of the packets from the Fermat Node to the multiple sink nodes. Aggregation is done at the Fermat Node where packets from multiple sources are collected and multiple input packets are converted into a single packet and henceforth transmitted to the multiple sinks as shown in Fig. 2(c).

      Fig. 2 (c) Data Agregation at the Fermat Node.

      By forwarding packets in such a fashion, the number of transmissions are reduced as well as the total number of bits transmitted is also reduced by n folds as compared to the number of bits received. Hence, this way of packet transmission saves energy which in turn enhances the lifetime of Multi-Sink Wireless Sensor Network. As discussed by the authors of [6], the transmitting and forwarding energy is directly proportional to the distance travelled by the packet and the number of bits transmitted. The equations of Energy transmission and forwarding are given below.

      Fig. 2 (b) Geocast Driven Scheme for more than two Geocast regions, Redrawn from [1].

      (2)

      (3)

      where, m is the packet size in number of bits, D is the duty cycle, d is the distance between two nodes, E is 50 nJ/bit and is 8.854 pJ/bit/sq. m.

3. THE GLOBAL MINIMA SCHEME

   As discussed in [1], the Global Minima Scheme finds the Fermat Point within a polygon by finding the minima of a function f(x,y) with respect to x and y, where f(x,y) calculates the summation of distances of all vertices of the polygon from an arbitrary point P(x,y) within that polygon. Finding the point P in the polygon enables us to get the Fermat Point for that particular polygon. By applying the minima function, the Global Minima Scheme helps us to find us to find the Fermat Point and hence the Fermat node for an n-sided polygon as shown in the Fig. 3(a). It overcomes the limitations of the Geometry driven scheme by eliminating the error factor induced for calculation of Fermat point for a n sided polygon.

   Fig.3(a) Fermat Point for an n-sided polygon.

   ig. 3(b) and Fig. 3(c).

   Fig.3(b) Comparison between the distance covered by packe

   ig. 3(b) and Fig. 3(c).

   Fig.3(b) Comparison between the distance covered by packe

   The Global Minima Algorithm performs better than the Geometry Driven scheme as it can be seen clearly from F

   t

   using Minima and Geometric method for different number of Geocast regions, redrawn from the results of [1].

   Fig.3(c) Comparison between the power consumed using Minima and Geometric method for different number of Geocast regions, redrawn

   from the results of [1].

   Moreover, the Minima method also overcomes the limitations of the Geometry Driven scheme which holds good only for triangles with angles less than 120. The calculation of Fermat Point for more than two Geocast regions in Geometry Driven scheme is also complex since a heuristic approach is followed. At the same time a generalized approach is followed in Minima method to find the Fermat Point of an n-sided polygon.

4. PACKET FORWARDING TECHNIQUES

   1. Greedy ForwardingTechnique

      In Greedy Forwarding technique, each node that receives the packet is required to transmit it to its neighboring node that has a minimum distance from the destination as the next node. In this way the packet is transmitted from hop to hop and finally reaches its destination.

   2. Compass Routing Forwarding Technique

      In Compass Routing technique, each node that receives the packet is required to transmit it to its neighboring node that has a minimum angle with the straight line joining the destination node with the node that is currently holding the data packet. In this way the packet is transmitted from hop to hop and finally reaches its destination.

   3. Kappa Forwarding Technique

      In Kappa Forwarding technique, each node that receives the packet is required to transmit it to its neighboring node that has the highest value of the forwarding potential () which is given as:

      = res_energy/dist (4) where, res_energy is the residual energy of a node in milli Joules and dist is the distance of a node from the destination in meters.

   4. Residual- Energy based ForwardingTechnique

   In Residual-Energy based Forwarding technique, the concept of residual energy is taken into consideration. Each node that receives the packet is required to transmit it to its neighboring node that has the highest value of residual energy.

5. VALIDATION OF THE GLOBAL MINIMA SCHEME In order to validate the Global Minima scheme, a region of 300×300 meters is taken into consideration. The sensor nodes are deployed in a Grid Fashion 30 meters apart from each other. Hence, total 100 sensor nodes are deployed over a two dimensional Cartesian plane. The transmission range of all the sensors is considered to be 35 meters. For the purpose of validation of the Minima method, the first sensor node Node1(30,30) is chosen as the source node and three sinks are taken into consideration that are placed at sensor node numbered 10 (300,30); 91(30,300)

   and 100(300,300) respectively as shown in Fig 4(a).

   Fig. 4(a) Sensor deployment with Fermat Point (FP) and Fermat Node (FN).

   The function that was validated first was concerned with the calculation of the Fermat Point (FP). By coding in MATLAB, the Fermat Point was found at the location (165,165) which was at a distance of 5.727565e+02 meters from the source node as shown in Fig. 4(b). The results obtained from the proposed Global Minima Scheme in [1] for the calculation of Fermat Point were also the same. Hence, the function to calculate the Fermat Point in Minima method is validated.

   The next function that was validated had the code to find the corresponding Fermat Node (FN) based on the obtained Fermat Point. In MATLAB, the Fermat Node was the sensor node Forty-five at the location (150,150) and was 2.121320e+01 meters away the Fermat Point as shown in Fig.4 (b). The Fermat Node obtained from the proposed Global Minima Scheme in [1] was Forty-four while the location was same (150,150). This difference is because in MATLAB the indexing starts from one and not from zero. Hence, the function to calculate the Fermat Node in Minima method is also validated.

   Fig. 4(b) Fermat Point (FX, FY) and Fermat Node (Nx, Ny).

   After the Fermat Point and Fermat Node were found, the transmission path for delivering packet from Source node to the sinks was validated. The transmission path for packet delivery was divided into two phases. Phase one included the transmission of the packet from source node to the Fermat Point while Phase two included the transmission of the packet from Fermat Node to multiple sink nodes. The path followed by the packet to reach the Fermat Node via multiple hops in transmission Phase one using MATLAB is shown in Fig. 4(c).

   Fig. 4(c) Hop to hop transmission of packet in Phase I

   The transmission path followed by the packet from source node to the Fermat Node in Global Minima Scheme is also the same. Henceforth, the path followed by the packet to reach multiple sinks from the Fermat Node in transmission Phase two using MATLAB as shown in Fig. 4(d), Fig. 4(e) and Fig.4(f) is also similar to that obtained using the Minima method. Hence, the complete path for packet delivery from source node to multiple sinks is also validated.

   Fig. 4(d) Transmission of packet in Phase II from Fermat Node to Sink 1.

   Fig. 4(e) Transmission of packet in Phase II from Fermat Node to Sink 2.

   Fig. 4(f) Transmission of packet in Phase II from Fermat Node to Sink 3.

6. CONCLUSION

The Minima Method is an efficient and effective way of locating the Fermat point and thereby the Fermat node for a polygonal sensor field in Wireless Sensor Networks. The functions to calculate Fermat Point, Fermat Node and the transmission path using the Global Minima Scheme are validated in MATLAB. The results obtained by using high level code in MATLAB are exactly similar to the results of the Minima method, with better visualization effects in MATLAB. As a result, we may conclude that the Global Minima scheme may be used for locating the Fermat point, marking the Fermat node as data aggregation center and for energy efficient packet transmission.

REFERENCES

1. Kaushik Ghosh, Sarbani Roy, ad Pradip K. Das, An Alternative Approach to Find the Fermat Point of a Polygonal Geographic Region for Energy Efficient Geocast Routing Protocols: Global Minima Scheme,In Networks and Communications, 2009.

   NETCOM09. First International Conference on (pp.332-337). IEEE

2. Young-Mi Song, Sung-Hee Lee, and Young-Bae Ko, FERMA: An Efficient Geocasting Protocol for Wireless Sensor Netwroks with Multiple Target Regions, Embedded and Ubiquitous Computing- EUC 2005 Workshops. Springler Berlin Heidelberg, 2005.

3. S.H. Lee and Y.B. Ko. Geometry-driven Scheme for Geocast Routing in Mobile Adhoc Networks, IEEE, vol.2,06/ 2006.

4. The Fermat point and generalizations. [Online]: http://www.cut-the- knot.org/generalization/fermat_point.shtml

5. Dan Pedoe, Geometry, a comprehensive course, Dover Publications, 1988.

6. Kaushik Ghosh, Pradip K. Das, and Sarmishtha Neogy, Effect of Source Selection, Deployment Pattern, and Data Forwarding Technique on Lifetime of Data Aggregating Multi-sink Wireless Sensor Network, Applied Computation and Security Systems, vol.1.

7. W.B. Heinzelman, A.P. Chandrakasan and H. Balakrishnana, An application-specific protocol architecture for wireless micro sensor networks,IEEE Transactions on Wireless Communications, Vol.1, Issue4,October2002.