Clustered Wireless Sensor Network in Precision Agriculture via Graph Theory

1  Introduction

Almost all forms of agriculture solely depend upon irrigation, as water is the most incredibly valuable and unavoidable resource for the plants to germinate, grow and yield. Hence it is supplied in surplus on most occasions in conventional farming that does not provide any method to ensure that the water resource is perfectly utilized directly by the root system of the plants. A large quantity of water will become waste or unused in the conventional agriculture adversely affecting the water cycle too and here arises the necessity of innovation for tackling the problem to have sustainable agriculture in which technology can be used for accurately analyzing the distribution of water as well as fertilizers right to the root system of the plants. Agriculture is considered to be one of the vital sources for all living beings. Nowadays environmental changes have tremendously shaken the entire globe. To overcome this, WSN takes an important role in the field of agriculture [1]. A sensors used in agriculture has been introduced in the last few decades to overcome such issues [2,3]. At present, researchers concentrate more on precision agriculture and smart agriculture used (WSNs) Wireless Sensor Networks. However, agricultural WSNs are still facing many challenges such as data quality, latency and multitasks, [4].

Innovation in the field of agriculture can be achieved through, modern technologies that help to assist communication and control within the devices. [5]. WSN which is structured and unstructured is one such dynamic technology that is widely used for monitoring agriculture as the radio range and the network connectivity change from time to time. The structured WSN can be properly deployed in a particular area and easily configured in case of the occurrence of any problem in any sensor nodes. In an unstructured WSN, causing complications in obtaining data and identifying the problems that arise in the sensor nodes. Though the WSN is dynamic, it exhibits many constraints such as message collision, bandwidth congestion and increased power consumption.

On the other hand, the routing table is frequently updated when changes occur in network topology [6]. Power and energy conservation in WSN is a challenging task where wasteful energy consumption causes overhead due to certain constraints like load balancing, idle listening, retransmitting, and generating control packets. Sensor Networks with wireless networks for efficient energy utilization, are crucial. As part of the Energy Efficiency function, data is transferred to the base station. Data is transferred utilising accurate power to each node using clustering algorithms and graph theory methodologies are utilised to recover the reliability of a network. WSNs pose a challenge to secure data aggregation.

To overcome these constraints, the clustering technique is considered to be one of the prominent methodologies. Finding out the most suitable and meaningful cluster in a large and complex network is a vital factor. The necessity of clustering is to partition the data into a certain number of groups with homogeneous characteristics under certain conditions.

This paper descriptively brings out such a meaningful cluster of sensor nodes controlled by the respective control stations using edge-fixed geodetic sets, which are determined by an algorithm with polynomial time complexity. Calculation of geodetic paths and nodes on geodetic paths in this algorithm is achieved by Floyd Warshall algorithm [7,8] with complexity O(n3).

In a connected graph G, the distance among two vertices x and y represented via d(x, y), is the length of the shortest x-y path in G. An x-y geodesic is a path of length d(x, y). For any vertex u of G, the eccentricity of u is e(u) = max{d(u, v) : v ∈V } [9]. A vertex v of G such that d(u,v) = e(u) is called an eccentric vertex of u. The set consisting of all vertices u which are adjacent to v is the neighborhood of v and is denoted by N(v) [10]. A maximal non-separable subgraph is a block of a graph. A set S ⊆V is a geodetic set if I[S] = V, where I[S] = ⋃x,y∈SI[x,y] . The minimum cardinality of a geodetic set is the geodetic number g(G). A g-set is a geodetic set of cardinality g(G). A set S ⊆ V in G is called a xy-geodominating set if every vertex of G lies on either an x–u geodesic or a y-u geodesic for some element u ∈ S. The xy-geodomination number of G is the minimum cardinality of a xy-geodominating set and is denoted by gxy(G). A gxy-set is an xy-geodominating set of cardinalities gxy(G).

2  Related Works

Network-based graph decomposition method is proposed to simplify the water supply system using a calibration tool. According to this mechanism, various connectivity properties are introduced in the field of analysis of the Water Supply System (WSS). Vertices of the graph are denoted as nodes and their connections as links. A genetic algorithm is used to solve a large complex problem, which proved to be an efficient optimization method.

Unpredictable climate change leads to scarcity of water. Since many countries face water scarcity, efficient water management for irrigation purposes is essential. The author keeping in mind the serious water crisis in the state of Andra Pradesh, an effective optimization technique, a Network-based optimization approach for irrigation systems has been developed from the (PDS) Pennar Delta System.

Graph theory was used to design the River-Lake System of Fenhu Industrial Park in China in 2018. The area is located located downstream of Taihu Lake, China’s second-largest lake, and is susceptible to flooding [11]. The river lakes connectivity evaluation is based of grap theory.

Based on various investigations, the author has given an overview of wireless sensor networks and their application. Recent developments in WSNs, and research problems in Wireless sensor networks have also been addressed. Obstacles in WSN are identified, and to be addressed in the future. The author has given an insight into the various standards and technologies available in WSN, and various other emerging technologies. WSN with IoT technology is used to connect the devices and collect and distribute the data. MQTT is simple and lightweight and is more advanced than HTTP.

Wireless Sensor Network application has been widely used in various fields [12]. The author has presented the usage of WSN in real-time applications in monitoring temperature, criminal activity on borders, pressure, and remote monitoring of patients. In addition, various challenges in WSN have also been presented, including power management, security and communication protocol and various issues.

A mathematical model [13] for the proper placement of the base station in WSN is built to increase the throughput. Base station placement algorithm for WSN is designed. Using the Successive Interference Cancellation (SIC) technique, the relationship between the distance between nodes and base stations is considered. The (LMID) likelihood Maximum inscribed disk algorithm is used to find the optimal position for the base station. The deterministic sensor placement to solve the area coverage problems is covered [14]. Several grid points are uniformly distributed and tried to place a minimum number of the sensor in the region. A greedy heuristic algorithm is used to place the sensors one via one in the position to each iteration.

Xiang et al (2021) [15] have established an information hiding based strategy for multi-index applications for security measures. The conversion of the information into keywords and from keywords to id are the process of the intended mechanism. As the conclusion the information is send as mixed index as the result of dispersion of the information’s which results in an secure data coverage. But the work still holds backlog as it cannot cover every data which may lead to security loss and must be optimized for performance improvement.

Qin et al (2021) [16] have proposed a big data based information hiding strategy for the data security. The latent dirichlet allocation methodology has been utilized for the processing of the information coverless data hiding which ensures security. The data feature extraction with the keyword generation along with keyword ID based on clustering has been utilized in the intended work. A rapid information hiding with secured bigdata strategy enables well established coverless information distribution but fails in covering the small details thus leads to performance degradation.

Analysis of clustering technique is used to improve energy consumption. Hybrid WSN method, especially for agriculture to deploy various nodes is experimented with. Experiments were conducted in soil, which has 35% silt, 15% clay and 50% sand. Several soil moistures were used for this experiment (5% to 25%) and three signal frequencies (433 MHz, 868 MHz and 915 MHz). A test model was developed that helps to determine the path loss and bit fault rate that operated under water contents and different frequencies.

In fields including as electrical and civil engineering, chemistry, social networks, and operational research, graph theory has become an essential methodology. Graphs are used in sensor networks, finance, or smart cities. Based on sensing positions, a vertex connectivity scheme is determined.

3  Edge Fixed Geodetic Sets

Researchers have utilized WSN technology in several areas to sense the environmental data. However, the agricultural land still faces some challenges, like open transmission medium, data routing, security, energy efficiency and limited battery power of sensors [17,18]. This paper focus to overcome such challenges by optimal control station placement. Edge fixed geodetic set concept is applied in the WSN for the optimal placement of control stations.

This research work presents a graph model of an irrigation network for agricultural applications, of more than 1000 hectors. To make the system proficient and cost effective, the over-all area is divided into different blocks, where each block is the collection of fields with multi crop farming. Soil can be better utilized to increase the crops production [19,20]. In such cases the most crucial challenge is to provide sufficient quantity of water to the fields based on needs. In the last few years, diverse researchers have focused on the problem proposed various mechanisms to sort out this issue. Proposed frame work include

•   Determine the water requirements of the agriculture field

•   Formation of edge fixed geodetic set

•   Optimal placement of control stations

Multi-crop farming [21] is established where farmers can plant crops as close together as possible to utilize all the available land. In this paper, sensors {s1,s2,…, sp}, are deployed in the agricultural land to sense the moist levels and the sensors {r1,r2,…, rm} are placed in the irrigation tank to monitor the water level to improve the water sharing system. Node deployment approaches are classified into two categories, Random deployment and planned deployment. Random deployment of sensor nodes is focused on in our study. The cluster head model architecture is exposed in Fig. 1

Figure 1: Architecture of the proposed system

Two irrigation tanks are placed in each block and the tanks in a selected block are mutually connected. Each field Fj is connected to any one of the tanks in the respective block. Moist sensors are placed at the root zone of the plant [22] which consumes comparatively more water. Depending upon the data provided by the sensors, necessary water is supplied to the entire field from the respective tank [23,24].

The network model contains a finite number of sensor nodes deployed in fields then control stations. Fig. 2 exposed the deployment of moist sensors is randomly distributed in the sensor field. Every sensor node after sensing the data sends the data to the Control Station. Subsequently, transfer a data towards the base station via a multi-hop direct transmission system depending on the distance among Cluster Nodes and the Control station.

Figure 2: Deployment of moist sensors in irrigation network

In order to, an effective supply of water, an automated water tank system is proposed. The water demand varies over time depending on various factors such as humidity, shading, type and size of plants and the quantity of air circulation. In certain situations more water supplies are necessary. In such a situation, the continuous supply of water may cause damage to pumps under different climatic conditions. To avert such hazards, the mutual connection of multi-tank is proposed. Thereby all the tanks placed in every block are mutually connected to share water among them according to the need and availability.

Due to uninterrupted communication with the base station, where there is a possibility of power drainage in sensors, which results in the inability to monitor the region that affects the effective distribution of water. To save the battery power, the placement of the control station is essential. We proposed a system with remote control valves and the valves at each field are controlled by its control stations. In addition, the control stations not only collect and store data about the usage of water in each field but also monitor the occurrence of interruption in connection as well as water loss. This paper brings to light the modeling of optimal placement of control stations using the edge fixed geodetic sets of a connected graph and the terminologies are tabulated in Tab. 1

3.1 Graph Modelling of Water Supply Network

Graphs are basic mathematical structures that are used to characterize data, signals, and processes ina a various domains. Graphs are mathematical structures made up of sets vertices and edges that are utilized to represent pairwise relations (edges) among numbers of objects (vertices) [25,26]. In general, a WSN described via an undirected graph G = (V, E), Therefore, path in the network can be regarded as set of nodes, which connects to each other from the source node to the destination node [27–29]. In this paper, we consider the nodes in WSN are stationary and each sensor has its own identical capabilities. With in the radio range, these nodes boost data transfer in WSN.

The proposed irrigation process network is an emerging next-generation (WMN) Wireless Mesh Network made up of numerous sensor nodes organized in a mesh topology as it has the advantage to communicate through any intermediate nodes even in the case of any node failure and it is modeled by a connected graph G(V,E), where V is the set of all sensors and E is the link between sensor nodes. The set V is partitioned into two subsets V1 and V2 such that

V1={si/si′sarethemoistsensorsplacedinthefield},

V2={ri/ri′sarethesensorsplacedintheirrigationtanksTi}

V=V1∪V2.

For each pair of nodes si,sj∈V1andrk,rl∈V2,sisj,sirl,rkrl∈E if and only if there is a communication link between each pair of vertices [25]. The set I[si,rm], consists of all sensor nodes lying on some si−rm geodesic.

The total irrigation system is modeled as a associated graph G(V,E). A sub network in each block is modeled as a subgraph G′(V1i∪V2i , Ei ), i is finite, where

V1i⊆V1 , V2i⊆V2 and ⋂i=1nV1i=∅ , ⋂i=1nV2i=∅ also Ei⊆E.

A method is proposed to cluster the sensors of subfields by fixing the edge rmrn∈Ei⊆E.

Steps:

1.    In the subfield Gi′ ( V1i∪V2i , Ei ), fix the edge ep=rmrn and find the minimum edge fixed geodetic set of the edge ep. Let it be represented by Efcs , there may be a finite number of Efcs for each edge. Let Ef={Efcsr/risfinite} be the set of all minimum edge fixed geodetic sets of the edge ep.

2.    Let Efcsr={s1,s2,s3,…,sn,}b e a minimum edge fixed geodetic set off the edge ep.

3.    Based on every element in Efcsr, clusters are made and every element in Efcsris assigned as CH. The each cluster head position is the optimum place to fix the control stations.

4.    Let Efcs1,Efcs2,Efcs3, …, Efcsr gives the minimum edge fixed geodetic sets of edge ep, each Efcsr act as control stations dynamically during a fixed period.

The proposed method of selecting cluster head by edge fixed geodetic set helps the optimum placement of control stations. For the sensors placed in the tank Ti and field Fj belongs to a particular block Bk , the extreme sensor nodes are found by calculating the maximum distance between the tank and moist sensors denoted by δ,δkij=max{d(ri,sj)/∀ri,sj∈Bk} , also the optimum distance between the edge rirj and the sensor sk,Δ(rirj,sk)=max{d(ri,sk),d(rj,sk)}. Extreme sensor nodes in each block are denoted by Psnbk and is defined as Psnbk = {sp/d(ri,sp)=δkipwhereri,spϵV′} .

Intermediary nodes between siandsjdenotedbyIc(si,sj) is the collection of sensor nodes in all the possible geodesic between si and sj . Floyd Warshall algorithm with polynomial complexity [30,31] is used to find δ and Ic(si,sj) . The cardinality |Efcsr| gives the number of elements in the set Efcsr.P rocedure to find Intermediary nodes Ic(ep,sj) between the edge ep=rirj and sensor node sjis given is Algorithm 1.

Consider a graph model of agricultural land with two blocks B1 and B2. Sensors s1,s2, s3,…, and s40 are deployed in different fields of blocks B1and B2. The tanks placed at B1 and B2 are T1, T2, T3 and T4. An edge fixed geodetic set of an edge r1r2in B1 is {s2,s3,s10}. By the proposed model the optimal position to place the control stations [32,33] at B1. The same procedure is repeated for B2 to fix the control stations and the optimum positions are { s5,s17, s29} and the graph representation of the irrigation process network is shown in Fig. 3 and the corresponding flowchart to find edge fixed geodetic set is shown in Fig. 4.

Figure 3: Graph representation of irrigation process network

Figure 4: Flowchart to find edge fixed geodetic set

The positions of elements in the set Efcsr(rvaries) are the optimal position for fixing control stations. The challenging task is, forming various clusters by assigning the elements in Efcsr(rvaries) cluster head.

The analysis had made for the network given in Fig. 5 and the resulting clusters are shown in Fig. 6.

Figure 5: Network with 40 nodes

Figure 6: Cluster formations

4  Simulation Results

This section presents the simulation setup of forming edge fixed geodetic clusters using Cup-carbon tool in Mat lab to measure the performance of the proposed irrigation process model using edge fixed geodetic sets. The results are evaluated, for block 1 and block 2. The performance clearly reveals that, energy required for communication of nodes per each signal is relatively low. The energy is efficiently saved, and efficient communication takes place within the node and cluster head without any interrupts. The proposed methodology can be carried out for larger networks. Figs. 7 and 9 shows the simulation results for clustering of block 1 and block 2. Figs. 8 and 10 gives the energy consumption of each sensor per signal in both block 1 and block 2.

Figure 7: Simulation for cluster formation of block 1 in irrigation network

Figure 8: Energy consumption of sensors in block 1

Figure 9: Simulation for cluster formation of block 2 in irrigation network

Figure 10: Energy consumption of sensors in block 2

Figs. 7 and 9 gives the edge fixed geodetic clusters for block 1 and block 2 of Fig. 3

5  Conclusion

This investigation deals with the issues about the Wireless sensor network that arose in the irrigation process. The main motive behind this study is to identify the anomalies related to power-saving and efficient irrigation in the fields where the multi-crop system is adopted. Based on shortest paths in graph theory, a new method of fixing stations and forming clusters using geodetic concepts reduces communication loss while increasing the communication efficiency of control stations by reducing the communication distance between stations. As a result of the simulation, the cost of energy per node of the edge-fixed geodetic cluster is less than 0.0225 joules per signal per node, indicating high performance between transmitters and receivers. From these results, it is evident that optimal placement of the control station along with the geodetic concepts in graph theory have strengthened a tremendous increase in the performance by reducing the energy consumption and thereby increasing the lifetime of sensors in the agrarian system.

Acknowledgement: We would like to thank the reviewers for their thoughtful comments and efforts towards improving our manuscript.

Funding Statement: The authors did not receive any funding for the research submitted.

Conflicts of Interest: The authors declare that they have no conflicts of interest to report regarding the present study.

References

 1.  D. D. K. Rathinam, D. Surendran, A. Shilpa, A. S. Grace and J. Sherin, “Modern agriculture using wireless sensor network (wsn),” in Proc. Int. Conf. on Advanced Computing & Communication Systems (ICACCS), Coimbatore, India, IEEE, pp. 515–519, 2019. [Google Scholar]

 2.  A. Z. Abbasi, N. Islam and Z. A. Shaikh, “A review of wireless sensors and networks’ applications in agriculture,” Computer Standards & Interfaces, vol. 36, no. 2, pp. 263–270, 2014. [Google Scholar]

 3.  H. M. Jawad, R. Nordin, S. K. Gharghan, A. M. Jawad and M. Ismail, “Energy-efficient wireless sensor networks for precision agriculture: A review,” Sensors, vol. 17, no. 8, pp. 1781, 2017. [Google Scholar]

 4.  X. Li, L. Zhu, X. Chu and H. Fu, “Edge computing-enabled wireless sensor networks for multiple data collection tasks in smart agriculture,” Journal of Sensors, vol. 2020, no. 1, pp. 9, 2020. [Google Scholar]

 5.  K. Haseeb, I. U. Din, A. Almogren and N. Islam, “An energy efficient and secure IoT-based WSN framework: An application to smart agriculture,” Sensors, vol. 20, no. 7, pp. 2081, 2020. [Google Scholar]

 6.  L. Shi, J. Zhang, Y. Shi, X. Ding and Z. Wei, “Optimal base station placement for wireless sensor networks with successive interference cancellation,” Sensors, vol. 15, no. 1, pp. 1676–1690, 2015. [Google Scholar]

 7.  J. Y. Yen, “Finding the k shortest loopless paths in a network,” Management Science, vol. 17, no. 11, pp. 712–716, 1971. [Google Scholar]

 8.  D. N. A. Mensah, H. Gao and L. W. Yang, “Approximation algorithm for shortest path in large social networks,” Algorithms, vol. 13, no. 2, pp. 36, 2020. [Google Scholar]

 9.  F. Harary, E. Loukakis and C. Tsouros, “The geodetic number of a graph,” Mathematical and Computer Modelling, vol. 17, no. 11, pp. 89–95, 1993. [Google Scholar]

10. A. Appathurai, R. Sundarasekar, C. Raja, E. J. Alex, C. A. Palagan et al., “An efficient optimal neural network-based moving vehicle detection in traffic video surveillance system,” Circuits Systems, and Signal Processing, vol. 39, no. 2, pp. 734–756, 2020. [Google Scholar]

11. P. Titus and A. P. Santhakumaran, “Monophonic distance in graphs,” IntechOpen, vol. 16, pp. 115–134, 2017. [Google Scholar]

12. A. P. Santhakumaran and P. Titus, “On the vertex geodomination number of a graph,” Ars Combinatoria, vol. 101, pp. 137–151, 2011. [Google Scholar]

13. A. P. Santhakumaran and P. Titus, “The edge fixed geodomination number of a graph,” An St. Univ. Ovidius Constanta, vol. 17, no. 1, pp. 187–200, 2009. [Google Scholar]

14. A. Murthy and G. Murthy, “A network flow model for irrigation water management,” Algorithmic Operations Research, vol. 7, no. 2, pp. 83–93, 2012. [Google Scholar]

15. L. Xiang, J. Qin, X. Xiang, Y. Tan and N. N. Xiong, “A robust text coverless information hiding based on multi-index method,” Intelligent Automation and Soft Computing, vol. 29, no. 3, pp. 899–914, 2021. [Google Scholar]

16. J. Qin, Z. Zhou, Y. Tan, X. Xiang and Z. He, “A big data text coverless information hiding based on topic distribution and TF-IDF,” International Journal of Digital Crime and Forensics (IJDCF), vol. 13, no. 4, pp. 40–56, 2021. [Google Scholar]

17. J. Chen, C. Xiao and D. Chen, “Connectivity evaluation and planning of a river-lake system in east China based on graph theory,” Mathematical Problems in Engineering, vol. 2018, no. 4, pp. 1–12, 2018. [Google Scholar]

18. A. Ali, Y. Ming, S. Chakraborty and S. Iram, “A comprehensive survey on real-time applications of WSN,” Future Internet, vol. 9, no. 4, pp. 77, 2017. [Google Scholar]

19. Y. Syafarinda, F. Akhadin, Z. E. Fitri, B. Widiawan and E. Rosdiana, “The precision agriculture based on wireless sensor network with MQTT protocol,” in Proc. IOP Conf. Series: Earth and Environmental Science, Bali, Indonesia, pp. 12059, 2018. [Google Scholar]

20. L. Shi, J. Zhang, Y. Shi, X. Ding and Z. Wei, “Optimal base station placement for wireless sensor networks with successive interference cancellation,” Sensors, vol. 15, no. 1, pp. 1676–1690, 2015. [Google Scholar]

21. S. S. Dhillon, K. Chakrabarty and S. S. Iyengar, “Sensor placement for grid coverage under imprecise detections,” in Proc. Int. Conf. on Information Fusion, Annapolis, MD, USA, pp. 1581–1587, 2002. [Google Scholar]

22. A. Bogdanov, E. Maneva and S. Riesenfeld, “Power-aware base station positioning for sensor networks,” in Proc. IEEE INFOCOM, China, Hong Kong, pp. 43–54, 2004. [Google Scholar]

23. A. Shahraki, A. Taherkordi, O. Haugen and F. Eliassen, “Clustering objectives in wireless sensor networks: A survey and research direction analysis,” Computer Networks, vol. 180, no. 3, pp. 107376, 2020. [Google Scholar]

24. L. Stankovic, D. Mandic, M. Dakovic, M. Brajovic, B. Scalzo et al., “Graph signal processing--part I: graphs, graph spectra, and spectral clustering,” vol. 2. Denmark: Springer, Cham, pp. 49, 2019. [Google Scholar]

25. X. Li, L. Zhu, X. Chu and H. Fu, “Edge computing-enabled wireless sensor networks for multiple data collection tasks in smart agriculture,” Journal of Sensors, vol. 2020, no. 3, pp. 1– 9, 2020. [Google Scholar]

26. D. Popescu, F. Stoican, G. Stamatescu, L. Ichim and C. Dragana, “Advanced UAV-WSN system for intelligent monitoring in precision agriculture,” Sensors, vol. 20, no. 3, pp. 817, 2020. [Google Scholar]

27. H. M. Jawad, R. Nordin, S. K. Gharghan, A. M. Jawad and M. Ismail, “Energy-efficient wireless sensor networks for precision agriculture: A review,” Sensors, vol. 17, no. 8, pp. 1781, 2017. [Google Scholar]

28. D. Shinghal and N. Srivastava, “Wireless sensor networks in agriculture: For potato farming,” Neelam, Wireless Sensor Networks in Agriculture: For Potato Farming, vol. 2, no. 8, pp. 3955–3963, 2017. [Google Scholar]

29. D. Shinghal and N. Srivastava, “Wireless sensor networks in agriculture: For potato farming,” International Journal of Engineering Science and Technolog, vol. 2, no. 8, pp. 3955–3963, 2010. [Google Scholar]

30. A. Appathurai, G. Manogaran and N. Chilamkurti, “Trusted FPGA-based transport traffic inject, impersonate (I 2) attacks beaconing in the Internet of Vehicles,” IET Networks, vol. 8, no. 3, pp. 169–178, 2019. [Google Scholar]

31. H. E. Egilmez, E. Pavez and A. Ortega, “Graph learning from data under laplacian and structural constraints,” IEEE Journal of Selected Topics in Signal Processing, vol. 11, no. 6, pp. 825–841, 2017. [Google Scholar]

32. M. Dursun and S. Ozden, “Optimization of soil moisture sensor placement for a PV-powered drip irrigation system using a genetic algorithm and artificial neural network,” Electrical Engineering, vol. 99, no. 1, pp. 407–419, 2017. [Google Scholar]

33. X. Yu, P. Wu, W. Han and Z. Zhang, “A survey on wireless sensor network infrastructure for agriculture,” Computer Standards & Interfaces, vol. 35, no. 1, pp. 59–64, 2013. [Google Scholar]