# Modified Floyd–Warshall’s Algorithm for Maximum Connectivity in Wireless Sensor Networks under Uncertainty

Authors: Laxminarayan Sahoo; Supriyan Sen; Kalishankar Tiwary; Sovan Samanta; Tapan Senapati
Journal: Discrete Dynamics in Nature and Society
 (2022)

---

## Abstract

The main objective of this paper is to find the duration of maximum time connectivity of sensor nodes under uncertainty utilizing the prespecified voltage/power of each sensor node. Wireless sensor networks (WSNs) are composed of nodes that transmit data between each other over routing. A variety of routing protocols and algorithms exist, each related to a particular set of conditions. There are a variety of routing algorithms available, some of which can be used in WSNs for routing. The goal of the fastest distance routing algorithms in a WSN is to use the least amount of energy possible. In a WSN, Dijkstra’s algorithm is typically used for shortest path routing. The Floyd–Warshall’s algorithm is used to compute the shortest paths between distinct nodes in a regular graph, but due to the absence of a communication mode, this algorithm is not ideal for routing in wireless networks. In this research work, we have considered a WSN to find out the maximum connectivity time utilizing optimum voltage. On the other hand, duration of connectivity and energy/voltage are two vital parameters that are difficult to manage. Because of limited resources and safety concerns, safety implementation is limited. Also, due to the irregular/hazardous environmental situations, the distance between sensor nodes and its voltage to link up the nodes are totally unpredictable. In this work, we employ triangular fuzzy numbers to express unpredictability. Then, utilizing defuzzification of fuzzy numbers, the associated WSN problem was transformed into a crisp one. The widely used signed distance approach has been applied for the defuzzification of fuzzy numbers in this case. To determine the best outcome and to illustrate the usefulness of the suggested technique, a numerical example has been solved using the modified Floyd–Warshall’s algorithm. Finally, concluding remarks on the proposed approach as well as future studies have been provided.


---

## Body

## 1. Introduction

A WSN is made up of many small devices known as nodes. All of those are sensitive enough to detect their environment, interpret, and transfer data to a designated pick-up location within a certain area. The nodes are connected directly with one another or with a base station (BS) located outside the area. The nodes’ battery, computational power, and bandwidth are all limited [1]. Energy minimization is the most important issue in WSN among all resource constraints. One of several main key objectives of WSN is to perform data transfer in an energy-efficient manner while striving to prolong the network’s life. The primary concern in these networks is power consumption. Instead of increasing channel capacity or decreasing the number of nodes, the central issue in these systems is prolonging network lifetime and resilience to chaotic phenomena [2, 3].Sensor nodes are made up of four types of units, viz. sensing units, processing units, communication units, and power units. Figure1 illustrates the fundamental design of a WSN node.Sensing units: sensors play a significant role in sensing devices by bridging the gap between the technological and physical domains. A sensor is a physical device that detects and responds to changes in the physical condition of an area of interest. Sensors perceive their surroundings, collect data, and convert it to fundamental data (current, voltage, and so on) before transmitting it to be analyzed further. It converts analog data (information gathered from the environment) to digital data, which is then delivered to the microcontroller for processing.Processing units: to accomplish the processing capabilities, the sensor node has a microcontroller with a processing unit, memory, converters, timer, and Universal Asynchronous Receive and Transmit (UART) interfaces. This unit is responsible for data acquisition, processing incoming and outgoing data, and establishing and modifying packet forwarding information based on communication performance.Communication unit: to enable connectivity, sensor nodes use radio frequencies or optical communication. Radio units in sensor nodes manage such an activity, using the electromagnetic spectrum to transmit information to their destinations. Generally, every sensor node transmits information directly to other nodes or sinks, or via multihop routing.Power units: the power units in the sensor node require energy for processing and data transmission. A node has a power unit that is responsible for supplying power to all of its units. The basic power consumption at the node is related to calculation and transmission, with transmission being the most power-intensive operation at the sensor node. Sensor nodes are typically battery-powered, but they can also harvest energy from renewable sources using solar cells.Figure 1
Design of WSN node.The work of Wang et al. [4] can indeed be referred to for more detail regarding sensor nodes (SNs). A sensor network’s design, deployment, and implementation necessitate an understanding of signal processing, connectivity and interfaces, systems integration, data security, and distributed algorithms. Additionally, WSNs include sensors that continuously monitor and transfer data or information regarding environmental or physical aspects like temperatures, moisture, sounds, and pressures to a centralized controller over a large distance [5]. The output signal is distributed to the control tower via the shortest available path that used appropriate wireless communication routing protocols [6]. WSN is particularly effective in situations when access or continuous monitoring is hampered by geographical boundaries or other physical factors.Generally, WSNs are positioned in challenging regions where battery restoration is problematic and personal monitoring is impossible. Numerous general concerns exist, including power conflict, allocated processing capacity, and diverse surroundings; electromagnetic affinities lead sensor nodes to malfunction intermittently [7]. Once all the installation is complete, all nodes keep monitoring the data, resulting in an exponential gain in battery performance. When a node detects an activity, it notifies another node or the central node via a confirmation. Furthermore, it demonstrates that equivalent knowledge is acquired from surrounding sensor nodes and from the base station that propagates the network’s flaw.Also, due to node deployment, transmission media, connectivity, network topology, coverage, data aggregation, quality of service (QoS), and other factors, sensor nodes have an impact on routing operations. The network’s performance is then assessed using quantified characteristics known as performance metrics. This, however, varies depending upon the requirements and type of sensor node (SN). However, there are a number of metrics that can be used to measure the success of WSNs. Table1 specifically explains a few of these metrics.Table 1
Several performance metrics in WSNs.
System lifetimeThe number of parameters in modeling that define the durability of the nodes is used to display the system lifetime. In sensor node, the most important factor is lifetime, hence energy should always be used as efficiently and effectively in all aspects of the node and network.LatencyData from provoked occurrences is commonly time-dependent, but in most circumstances, recurrent sensing is tolerable since the resulting latency is only a matter of seconds.QualityThe end-user never needs all of the data; only the incident data are then processed in BS for analysis. As a result, the network’s quality is influenced by the data aggregation architecture and protocols utilized, as well as the application’s specific requirements.Delay and delay variationDelay is defined as it takes to send and receive a data packets packet from one node to another, while delay variation is the time it takes for a delay metric to change in relation to some standard value. Information gathering from nodes to the BS and interpretation in the BS are both concerned about delays in sensor networks.Bandwidth, capacity, and throughputThese represent the amount of data that can be sent through a network in a given amount of time; however, because the data are so little, bandwidth is rarely an issue.Hop countThe number of hops in communication takes into account the cost of the path and, subsequently, the amount of energy used in the transmission.Signal strengthSignal-to-noise ratio (SNR) is being used to compute and identify the nodes and their accessibility during the process of communication as a measure of connection quality and distance between two nodes.Ease of deploymentSensor networks are made up of a small number of sensors that must be able to communicate with each other even when there is no traditional networks infrastructure.Data redundancy of data is a significant concern in WSNs; to minimize data recurrence and to build a strong network, various routing methods with distinct methodologies have previously been proposed in this study [8]. One of these efficient techniques is the cluster-based routing protocol, which divides sensor nodes into many bundles, each of which is referred to as a cluster. Choose a leading node in each cluster to serve as the Cluster Head. When any sensor node detects an action in the environment, it sends a notification to the relating cluster heads. The message is being sent to the cell tower by the cluster heads. As a result, choosing the right cluster head can reduce the amount of energy lost considerably. WSNs with a compact footprint can provide a low-cost, low-power communication network in a limited space. Additionally, wireless communication is growing in importance in today’s society, as it is used in a variety of crucial transactions. Duration of connectivity and energy are two major parameters that are difficult to manage. Because of limited resources and safety concerns, safety implementation is limited. Other media’s routing protocols cannot be used on a WSN. Instead, routing should be carried out in an energy-efficient manner. Such networks have a wide range of applications, including military, security, and home applications, among others [9–13]. The renowned works of Praveen Kumar et al. [14, 15] and Sah et al. [16] might be referenced for more information. Considerable influences of the different authors towards the WSNs problem are listed in Table 2.Table 2
Significance influence of the different authors towards WSNs.
ReferencesYearSignificance influenceDijkstra [17]1959A note on two problems in connexion with graphsFeeney [18]2001An energy-consumption model for routing protocol performance analysis in mobile ad hoc networksMainwaring et al. [10]2002WSNs for habitat monitoringIntanagonwiwat et al. [19]2003WSN directed diffusionAkyildiz et al. [11]2007A survey of wireless multimedia sensor networksFarahani [6]2008ZigBee wireless networks and transceiversChamp and Saad [20]2008Geographic routing with location errors in WSNs: an energy-efficient approachFlammini et al. [13]2009Sensor networks, both wired and wireless, for industrial applicationsAttarde et al. [21]2010A WSN with an improved spanning-tree topologyDoohan et al. [22]2011The shortest path routing protocol (SPRP) for highly data-centric WSNsMusznicki et al. [23]2012WSN routing algorithm in an interference environmentSalvatore and Yang [24]2012Localized multicast routing based on Dijkstra in WSNsRamson and Moni [25]2017WSN applicationsPraveen Kumar et al. [14]2019An overview of machine learning algorithms for wireless sensor networksXu et al. [26]2020CUF-based FEM analysis of thin-wall structures with Lagrange polynomial expansionRaman et al. [27]2020An overview of the WSN routing techniquesYu et al. [28]2020WSN secure directed diffusion routing protocol based on trustDaanoune et al. [29]2021LEACH-based clustering routing protocols in WSNsUllah [30]2021Energy-efficient clustering protocols based on hybrid, energy-efficient, and distributed (HEED) technology for WSNsSah et al. [16]2021EDGF: empirical dataset generation framework for wireless network networksPraveen Kumar et al. [15]2021An extended ACO-based mobile sink path determination in wireless sensor networks


### 1.1. Motivation

In WSNs, it has been generally assumed that the parameters relating to the communication system are precisely valued such as distance between sensor nodes, voltage, energy consumption. However, because of the anomalous climate factors, it is possible that all of the characteristics of the WSNs will not be rectified. Furthermore, due to the different geographical situations, the distance between sensor nodes and its voltage to link up the nodes are completely unexpected. Motivated from this fact, the issue can be viewed through the lens of uncertainty, with times and voltages treated as unspecific/ambiguous in nature. In such rare situations, fuzzy set theory comes in handy to deal with the situation. Zadeh [31] established the notion of fuzzy set in 1965, and it has proven to be effective in dealing with inaccuracy and ambiguity in real-life circumstances. Bellman and Zadeh [32] established the notion of stance with uncertainty in 1970. Here, we considered uncertain times/voltages using fuzzy numbers. As a result, the fuzzy WSN issue creates a basis for efficiently solving real-world WSN challenges with unclear parameters. To represent unpredictability, several techniques have been utilized in the literature, including interval, fuzzy, stochastic, and fuzzy-stochastic approaches. Several researchers have formulated and solved WSNs problems by considering fuzzy parameters. For details, Table 3 summarizes the authors’ considerable effects on WSN in a fuzzy environment.Table 3
Significance influences of the different authors towards WSNs problem under fuzzy environment.
ReferencesYearSignificance influenceTorfi et al. [33]2010Fuzzy AHP is being used to measure the relative weights of evaluation criteria, and fuzzy TOPSIS is used to rank the alternativesBagci and Yazici [34]2010For WSNs, an energy-aware fuzzy unequal clustering algorithmTaheri et al. [35]2012A fuzzy logic-based energy-aware distributed clustering protocol for WSNsAzad and Sharma [36]2013Cluster head selection in WSNs under fuzzy environmentPurusothaman and Sivakumar [37]2013Localization in WSNs using fuzzy RSSIBagci and Yazici [38]2013A fuzzy approach to unequal clustering in WSNs that considers energyGotefode and Kolhe [39]2015Energy efficiency in WSN using fuzzy rule and tree-based routing protocolNagarajan et al. [40]2015WSN lifetime extension using fuzzy clustering and intrusion detection using EASPushpalatha and Nayak [41]2015A clustering algorithm for WSNs using a Type-2 fuzzy logic model to optimize network lifetimeSethi and Dhillon [42]2016Using a fuzzy-based technique, energy-efficient clustering is used to improve network lifetime in WSNsUppal and Kaur [43]2016Fuzzy link cost measurement in WSNs for energy-efficient routingBalakrishnan and Balachandran [44]2017Fuzzy logic based energy-efficient clustering hierarchy for nonuniform WSNsEl-Alami and Najid [45]2017Clustering algorithm for WSNs based on fuzzy logicShokrollahi et al. [46]2017An energy-efficient clustering algorithm for WSNs using fuzzy C-Means and genetic fuzzy systemMirzaie and Mazinani [47]2018In a WSN, an energy-efficient multiclustering algorithm based on fuzzy logicWang et al. [48]2018Spectral partitioning and fuzzy C-means based clustering algorithm for big data WSNsAli and Gared [49]2019Neuro-fuzzy algorithms are used to optimise the energy consumption of a WSNLata et al. [50]2020Fuzzy clustering algorithm for improving WSN reliability and network lifetimeIn this work, we employ triangular fuzzy numbers to express unpredictability. Then, utilizing the defuzzification of fuzzy numbers, the associated WSN problem was transformed into a crisp one. The widely used signed distance approach [51] has been applied to defuzzify the fuzzy number in this case. In this paper, a modified Floyd–Warshall’s algorithm is proposed for finding the duration of maximum time connectivity of sensor nodes using prespecified voltage/power of each sensor node. By selecting the most trusted optimal path and connectivity, the proposed routing scheme extends network durability. To determine the best outcome and to demonstrate the applicability of the suggested method, a mathematical formulation has been addressed. Finally, the proposed approach’s concluding remarks and future research have been given.


### 1.2. Contributions

The following are the contributions of the proposed research work:(1)
We developed and solved the WSNs issue in the presence of uncertainty(2)
We used fuzzy sets/fuzzy numbers to convey uncertainty(3)
To express all of the parameters, such as the distance between sensor nodes and the voltage/power required to connect the nodes, we used Triangular Fuzzy Numbers (TFNs)(4)
The defuzzification of fuzzy parameters has been accomplished using the signed distance method(5)
For determining the period of maximum time connectivity of sensor nodes, a modified Floyd–Warshall algorithm has been implemented(6)
In a fuzzy context, a modified Floyd–Warshall algorithm has been described(7)
χ2-test has been carried out in order to discuss the numerical result(8)
Concluding remarks have been presented, along with the future direction of the proposed research workMost of the work carried out in this study can be summarized in this way:(i)
In WSNs, the distance between sensor nodes and its voltage/power to link up the nodes are considered as TFNs(ii)
Signed-distance method has been employed to defuzzification of fuzzy parameters(iii)
A modified Floyd–Warshall’s algorithm is proposed for finding the duration of maximum time connectivity of sensor nodes using prespecified voltage/power of each sensor nodeThe remaining part of the paper is arranged as follows: Section2 provides some basic mathematical foundations of fuzzy sets. Section 3 contains assumptions and notations. Section 4 addressed a modified Floyd–Warshall’s algorithm for the intention of solution methodology. Section 5 presented a problem description in a fuzzy environment. Section 6 presents a numerical example to illustrate the relationship between the result and the explanation. Section 7 possesses the conclusions of this study along with the future direction of the proposed research.


## 1.1. Motivation

In WSNs, it has been generally assumed that the parameters relating to the communication system are precisely valued such as distance between sensor nodes, voltage, energy consumption. However, because of the anomalous climate factors, it is possible that all of the characteristics of the WSNs will not be rectified. Furthermore, due to the different geographical situations, the distance between sensor nodes and its voltage to link up the nodes are completely unexpected. Motivated from this fact, the issue can be viewed through the lens of uncertainty, with times and voltages treated as unspecific/ambiguous in nature. In such rare situations, fuzzy set theory comes in handy to deal with the situation. Zadeh [31] established the notion of fuzzy set in 1965, and it has proven to be effective in dealing with inaccuracy and ambiguity in real-life circumstances. Bellman and Zadeh [32] established the notion of stance with uncertainty in 1970. Here, we considered uncertain times/voltages using fuzzy numbers. As a result, the fuzzy WSN issue creates a basis for efficiently solving real-world WSN challenges with unclear parameters. To represent unpredictability, several techniques have been utilized in the literature, including interval, fuzzy, stochastic, and fuzzy-stochastic approaches. Several researchers have formulated and solved WSNs problems by considering fuzzy parameters. For details, Table 3 summarizes the authors’ considerable effects on WSN in a fuzzy environment.Table 3
Significance influences of the different authors towards WSNs problem under fuzzy environment.
ReferencesYearSignificance influenceTorfi et al. [33]2010Fuzzy AHP is being used to measure the relative weights of evaluation criteria, and fuzzy TOPSIS is used to rank the alternativesBagci and Yazici [34]2010For WSNs, an energy-aware fuzzy unequal clustering algorithmTaheri et al. [35]2012A fuzzy logic-based energy-aware distributed clustering protocol for WSNsAzad and Sharma [36]2013Cluster head selection in WSNs under fuzzy environmentPurusothaman and Sivakumar [37]2013Localization in WSNs using fuzzy RSSIBagci and Yazici [38]2013A fuzzy approach to unequal clustering in WSNs that considers energyGotefode and Kolhe [39]2015Energy efficiency in WSN using fuzzy rule and tree-based routing protocolNagarajan et al. [40]2015WSN lifetime extension using fuzzy clustering and intrusion detection using EASPushpalatha and Nayak [41]2015A clustering algorithm for WSNs using a Type-2 fuzzy logic model to optimize network lifetimeSethi and Dhillon [42]2016Using a fuzzy-based technique, energy-efficient clustering is used to improve network lifetime in WSNsUppal and Kaur [43]2016Fuzzy link cost measurement in WSNs for energy-efficient routingBalakrishnan and Balachandran [44]2017Fuzzy logic based energy-efficient clustering hierarchy for nonuniform WSNsEl-Alami and Najid [45]2017Clustering algorithm for WSNs based on fuzzy logicShokrollahi et al. [46]2017An energy-efficient clustering algorithm for WSNs using fuzzy C-Means and genetic fuzzy systemMirzaie and Mazinani [47]2018In a WSN, an energy-efficient multiclustering algorithm based on fuzzy logicWang et al. [48]2018Spectral partitioning and fuzzy C-means based clustering algorithm for big data WSNsAli and Gared [49]2019Neuro-fuzzy algorithms are used to optimise the energy consumption of a WSNLata et al. [50]2020Fuzzy clustering algorithm for improving WSN reliability and network lifetimeIn this work, we employ triangular fuzzy numbers to express unpredictability. Then, utilizing the defuzzification of fuzzy numbers, the associated WSN problem was transformed into a crisp one. The widely used signed distance approach [51] has been applied to defuzzify the fuzzy number in this case. In this paper, a modified Floyd–Warshall’s algorithm is proposed for finding the duration of maximum time connectivity of sensor nodes using prespecified voltage/power of each sensor node. By selecting the most trusted optimal path and connectivity, the proposed routing scheme extends network durability. To determine the best outcome and to demonstrate the applicability of the suggested method, a mathematical formulation has been addressed. Finally, the proposed approach’s concluding remarks and future research have been given.


## 1.2. Contributions

The following are the contributions of the proposed research work:(1)
We developed and solved the WSNs issue in the presence of uncertainty(2)
We used fuzzy sets/fuzzy numbers to convey uncertainty(3)
To express all of the parameters, such as the distance between sensor nodes and the voltage/power required to connect the nodes, we used Triangular Fuzzy Numbers (TFNs)(4)
The defuzzification of fuzzy parameters has been accomplished using the signed distance method(5)
For determining the period of maximum time connectivity of sensor nodes, a modified Floyd–Warshall algorithm has been implemented(6)
In a fuzzy context, a modified Floyd–Warshall algorithm has been described(7)
χ2-test has been carried out in order to discuss the numerical result(8)
Concluding remarks have been presented, along with the future direction of the proposed research workMost of the work carried out in this study can be summarized in this way:(i)
In WSNs, the distance between sensor nodes and its voltage/power to link up the nodes are considered as TFNs(ii)
Signed-distance method has been employed to defuzzification of fuzzy parameters(iii)
A modified Floyd–Warshall’s algorithm is proposed for finding the duration of maximum time connectivity of sensor nodes using prespecified voltage/power of each sensor nodeThe remaining part of the paper is arranged as follows: Section2 provides some basic mathematical foundations of fuzzy sets. Section 3 contains assumptions and notations. Section 4 addressed a modified Floyd–Warshall’s algorithm for the intention of solution methodology. Section 5 presented a problem description in a fuzzy environment. Section 6 presents a numerical example to illustrate the relationship between the result and the explanation. Section 7 possesses the conclusions of this study along with the future direction of the proposed research.


## 2. Basic Mathematical Foundations

This section outlines certain terminology and basic ideas linked to fuzzy sets, fuzzy numbers, and the signed distance method adopted for this research.


### 2.1. Definitions of the Term Fuzzy Set

A membership functionμA˜x that maps each element x in X to a real number in the interval 0≤x≤1 forms a fuzzy set. The function μA˜x represents the degree of membership of x in the fuzzy set A˜.Definition 1.
Theα-cut of a fuzzy set A˜ is a crisp subset of X and is denoted by Aα=x∈X:μA˜x≥α, where μA˜x is the membership function of A˜ and α∈0,1.Definition 2.
A fuzzy setA˜ is called a normal fuzzy set if there exists at least one x∈X such that μA˜x=1.Definition 3.
A fuzzy setA˜ is called convex if for every pair of x1,, x2∈X, the membership function of A˜ satisfies μA˜λx1+1−λx2≥minμA˜x1,μA˜x2, where λ∈0,1.Definition 4.
A fuzzy numberA˜ is a fuzzy set that is both convex and normal.Definition 5.
The triangular fuzzy number (TFN) is a normal fuzzy number denoted asA˜=al,am,ar where al≤am≤ar and its membership function μA˜x:X⟶0,1 is defined by(1)μA˜x=x−alam−alifal≤x≤am,1ifx=am,ar−xar−amifam≤x≤ar.


### 2.2.α Level Set of Triangular Fuzzy Number

LetA˜=al,am,ar be a triangular fuzzy number, then α level set of the triangular fuzzy number A˜=al,am,ar is Aα=x∈X:μA˜x≥α=Aα−,Aα+, where Aα−=al+am−alα and Aα+=ar−ar−amα, α∈0,1. Now, we can represent A˜=al,am,ar as A˜=∪α∈0,1Aα. We can derive the signed distance [51] from Aα−,Aα+ to 0˜ as DAα,0˜=1/2Aα−+Aα+.LetC˜ be a fuzzy set on X. We denote Cα=Cα−,Cα+ as the α-cut off C˜, α∈0,1. Now, for each α∈0,1, Cα− and Cα+ uniquely exist and are integrable. In addition to that let F be the family of all these fuzzy sets C˜ on X. Consequently, we have the following definition.Definition 6.
LetC˜∈F, we defined the signed distance of C˜ measured from 0˜ as DC˜,0˜=1/2∫01Cα−+Cα+dα.Remark 1.
LetC˜=cl,cm,cr be the triangular fuzzy number then Cα−=cl+cm−clα and Cα+=cr−cr−cmα, respectively where α∈0,1. Cα− and Cα+ exist and are integrable for α∈0,1. Therefore, C˜∈F and by the definition, we have DC˜,0˜=1/2∫01Cα−+Cα+dα=1/4cl+2cm+cr.


### 2.3. Chi-Square Test Statistics

To perform the Chi-square test of independence, we need to have the following steps:Step 1: computeχ2=∑i=1m∑j=1nxij−x¯ij2/x¯ij, where xij is the observed value and x¯ij is the expected value in the i-th row and j-th column of the bivariate dataStep 2:x¯ij=∑i=1mxij∑j=1nxij/∑i=1m∑j=1nxijStep 3: calculateγ=degree of freedom=m−1n−1Step 4: calculate thep value and set level of significance αStep 5: stated null hypothesisH0 and alternative hypothesis H1Step 6: ifp<α, then reject H0 and accept H1 otherwise do not have enough evidence to reject H0


## 2.1. Definitions of the Term Fuzzy Set

A membership functionμA˜x that maps each element x in X to a real number in the interval 0≤x≤1 forms a fuzzy set. The function μA˜x represents the degree of membership of x in the fuzzy set A˜.Definition 1.
Theα-cut of a fuzzy set A˜ is a crisp subset of X and is denoted by Aα=x∈X:μA˜x≥α, where μA˜x is the membership function of A˜ and α∈0,1.Definition 2.
A fuzzy setA˜ is called a normal fuzzy set if there exists at least one x∈X such that μA˜x=1.Definition 3.
A fuzzy setA˜ is called convex if for every pair of x1,, x2∈X, the membership function of A˜ satisfies μA˜λx1+1−λx2≥minμA˜x1,μA˜x2, where λ∈0,1.Definition 4.
A fuzzy numberA˜ is a fuzzy set that is both convex and normal.Definition 5.
The triangular fuzzy number (TFN) is a normal fuzzy number denoted asA˜=al,am,ar where al≤am≤ar and its membership function μA˜x:X⟶0,1 is defined by(1)μA˜x=x−alam−alifal≤x≤am,1ifx=am,ar−xar−amifam≤x≤ar.


## 2.2.α Level Set of Triangular Fuzzy Number

LetA˜=al,am,ar be a triangular fuzzy number, then α level set of the triangular fuzzy number A˜=al,am,ar is Aα=x∈X:μA˜x≥α=Aα−,Aα+, where Aα−=al+am−alα and Aα+=ar−ar−amα, α∈0,1. Now, we can represent A˜=al,am,ar as A˜=∪α∈0,1Aα. We can derive the signed distance [51] from Aα−,Aα+ to 0˜ as DAα,0˜=1/2Aα−+Aα+.LetC˜ be a fuzzy set on X. We denote Cα=Cα−,Cα+ as the α-cut off C˜, α∈0,1. Now, for each α∈0,1, Cα− and Cα+ uniquely exist and are integrable. In addition to that let F be the family of all these fuzzy sets C˜ on X. Consequently, we have the following definition.Definition 6.
LetC˜∈F, we defined the signed distance of C˜ measured from 0˜ as DC˜,0˜=1/2∫01Cα−+Cα+dα.Remark 1.
LetC˜=cl,cm,cr be the triangular fuzzy number then Cα−=cl+cm−clα and Cα+=cr−cr−cmα, respectively where α∈0,1. Cα− and Cα+ exist and are integrable for α∈0,1. Therefore, C˜∈F and by the definition, we have DC˜,0˜=1/2∫01Cα−+Cα+dα=1/4cl+2cm+cr.


## 2.3. Chi-Square Test Statistics

To perform the Chi-square test of independence, we need to have the following steps:Step 1: computeχ2=∑i=1m∑j=1nxij−x¯ij2/x¯ij, where xij is the observed value and x¯ij is the expected value in the i-th row and j-th column of the bivariate dataStep 2:x¯ij=∑i=1mxij∑j=1nxij/∑i=1m∑j=1nxijStep 3: calculateγ=degree of freedom=m−1n−1Step 4: calculate thep value and set level of significance αStep 5: stated null hypothesisH0 and alternative hypothesis H1Step 6: ifp<α, then reject H0 and accept H1 otherwise do not have enough evidence to reject H0


## 3. Assumptions and Notations

We considered the following assumptions and notations while writing the entire paper:


### 3.1. Assumptions

(i)
The Links distance between every pair of sensor nodes is always the same and triangular fuzzy number(ii)
The sensor node can change its position after its deployment(iii)
Every sensor node discharges its energy/power depending on its prefixed rate which is also a triangular fuzzy number


### 3.2. Notations

d˜ij The distance/weight of a path from sensor node i to jd˜ij′ The distance/weight of a path from sensor node j to iQ˜i Energy/power capacity of i-th node (in percent)Q˜j Energy/power capacity of j-th node (in percent)q˜i Rate of discharge of energy/power per unit time of i-th nodeq˜j Rate of discharge of energy/power per unit time of j-th nodet˜ij The time that a sensor node i can hold the connection to the sensor node jt˜ij′ The time that a sensor node j can hold the connection to the sensor node i


## 3.1. Assumptions

(i)
The Links distance between every pair of sensor nodes is always the same and triangular fuzzy number(ii)
The sensor node can change its position after its deployment(iii)
Every sensor node discharges its energy/power depending on its prefixed rate which is also a triangular fuzzy number


## 3.2. Notations

d˜ij The distance/weight of a path from sensor node i to jd˜ij′ The distance/weight of a path from sensor node j to iQ˜i Energy/power capacity of i-th node (in percent)Q˜j Energy/power capacity of j-th node (in percent)q˜i Rate of discharge of energy/power per unit time of i-th nodeq˜j Rate of discharge of energy/power per unit time of j-th nodet˜ij The time that a sensor node i can hold the connection to the sensor node jt˜ij′ The time that a sensor node j can hold the connection to the sensor node i


## 4. Modified Floyd–Warshall's Algorithm for the Intention of Solution Methodology

### 4.1. Modified Floyd–Warshall’s Algorithm

Lettij be the maximum connectivity time that a sensor node can hold the connection from sensor node i to sensor node j for all intermediate sensor nodes are in the set 1,2,…,k. When k=0, a path from vertices i to j with no intermediate vertices numbered higher than no intermediate at all. Such a time path has at most one edge and consequently tij0=wijNow the recursive definition is as follows:(2)tij=wij,ifk=0,maxtij,mintik+tkj,ifk≥1.Now our aim is to findTn=tijn which gives the maximum time connectivity from vertices i to j where intermediate vertices are in the set 1,2,............nThe pseudo code for a modified Floyd–Warshall’s algorithm is given as follows:(3)Modified Floyd−WarshallW,n,n⟵rowsW,n,T0⟵W,fork⟵1ton,do fori⟵1ton,do forj⟵1ton,dotijk⟵maxtijk−1,mintikk−1+tkjk−1,returnTn.


### 4.2. Modified Floyd–Warshall’s Algorithm in Fuzzy Environment

To solve our proposed WSN problem under a fuzzy environment we have implemented a modified Floyd–Warshall’s algorithm in a fuzzy environment. The pseudo code of this algorithm is as follows:(4)Modified Floyd−WarshallDW˜,0˜,n,n⟵rowsDW˜,0˜,n,DT˜0,0˜⟵DW˜,0˜,fork⟵1ton,do fori⟵1ton,do forj⟵1ton,doDt˜ijk,0˜⟵maxDt˜ijk−1,0˜,minDt˜ikk−1,0˜+Dt˜kjk−1,0˜,returnDT˜n,0˜.


### 4.3. Time Complexity Analysis of Modified Floyd–Warshall’s Algorithm in Fuzzy Environment

Letn be the number of vertices/nodes in a WSN. To find the current value of Dt˜ijk,0˜, we need to compute maxDt˜ijk−1,0˜,minDt˜ikk−1,0˜+Dt˜kjk−1,0˜, which is an n×n matrix already computed in the previous stage, Hence, the time complexity is On2. Now to find all pair maximum connectivity time for the entire WSN, we need to compute n such matrix. Again, to compute DT˜n,0˜ we need n2 computation each computation takes a constant amount of time. Hence, the total time complexity to compute the algorithm is nOn2+cOn2≃On3.


## 4.1. Modified Floyd–Warshall’s Algorithm

Lettij be the maximum connectivity time that a sensor node can hold the connection from sensor node i to sensor node j for all intermediate sensor nodes are in the set 1,2,…,k. When k=0, a path from vertices i to j with no intermediate vertices numbered higher than no intermediate at all. Such a time path has at most one edge and consequently tij0=wijNow the recursive definition is as follows:(2)tij=wij,ifk=0,maxtij,mintik+tkj,ifk≥1.Now our aim is to findTn=tijn which gives the maximum time connectivity from vertices i to j where intermediate vertices are in the set 1,2,............nThe pseudo code for a modified Floyd–Warshall’s algorithm is given as follows:(3)Modified Floyd−WarshallW,n,n⟵rowsW,n,T0⟵W,fork⟵1ton,do fori⟵1ton,do forj⟵1ton,dotijk⟵maxtijk−1,mintikk−1+tkjk−1,returnTn.


## 4.2. Modified Floyd–Warshall’s Algorithm in Fuzzy Environment

To solve our proposed WSN problem under a fuzzy environment we have implemented a modified Floyd–Warshall’s algorithm in a fuzzy environment. The pseudo code of this algorithm is as follows:(4)Modified Floyd−WarshallDW˜,0˜,n,n⟵rowsDW˜,0˜,n,DT˜0,0˜⟵DW˜,0˜,fork⟵1ton,do fori⟵1ton,do forj⟵1ton,doDt˜ijk,0˜⟵maxDt˜ijk−1,0˜,minDt˜ikk−1,0˜+Dt˜kjk−1,0˜,returnDT˜n,0˜.


## 4.3. Time Complexity Analysis of Modified Floyd–Warshall’s Algorithm in Fuzzy Environment

Letn be the number of vertices/nodes in a WSN. To find the current value of Dt˜ijk,0˜, we need to compute maxDt˜ijk−1,0˜,minDt˜ikk−1,0˜+Dt˜kjk−1,0˜, which is an n×n matrix already computed in the previous stage, Hence, the time complexity is On2. Now to find all pair maximum connectivity time for the entire WSN, we need to compute n such matrix. Again, to compute DT˜n,0˜ we need n2 computation each computation takes a constant amount of time. Hence, the total time complexity to compute the algorithm is nOn2+cOn2≃On3.


## 5. Problem Description in Fuzzy Environment

Let us assume that a WSN communicated with the help ofE=e1,e2,…,e2n distinct link over V=v1,v2,…,vn distinct sensor node. Furthermore, assume that the distance between any two sensor nodes is d˜ij from i to j and d˜ij′ from j to i. We also assume that the distance d˜ij and d˜ij′ may be different because of node displacement. Here, source node i and sink sensor node j are discharging their charges at a rate of q˜i and q˜j over the link per unit distance (see Figure 2). Let t˜ijk be the time that a sensor node can hold the connection from sensor node i to sensor node j for all intermediate sensor nodes are in the set 1,2,…,k. Then the amount of time that the sensor node can hold the connection represented as t˜ij can be calculated as t˜ij=Q˜i/q˜id˜ij for sensor nodes i to j and t˜ji=Q˜j/q˜jd˜ij′ for sensor nodes j to i. Therefore, our aim is to find all pairs’ maximum link holding time so that the entire WSN system can be in an operative state. Therefore, the corresponding problem is defined recursively as follows:(5)t˜ijk=t˜ij,ifk=0,maxt˜ijk−1,mint˜ikk−1,t˜kjk−1,ifk≥1,.Figure 2
Communication with source sensor nodei and sink sensor node j.


## 6. Result and Discussion with a Numerical Example

To illustrate the proposed solution procedure, we have considered the following example:Presume there is a WSN comprised of six sensor nodes (see Figure3). We also presume that every node is located in a separate place. The network has twelve links, and the distance of each link is measured in meters which is also a triangular fuzzy number. Figure 1 depicts the existence of an acknowledgement link between each pair of sensor nodes. Besides this, the link length is the same for each pair of nodes, but the acknowledgement link length may vary from the sender link because all sensor nodes are deployed. All input data have been given in Table 4 and 5.Figure 3
WSN is comprised of six sensor nodes.Table 4
Weight matrixW˜=d˜ij6×6.
Sensor node1234561(0, 0, 0)(7, 9, 12)——(15, 16, 18)—2(7, 9, 12)(0, 0, 0)(8, 11, 13)———3—(8, 11, 13)(0, 0, 0)——(7, 8, 10)4———(0, 0, 0)(4, 7, 9)—5(15, 16, 18)——(4, 7, 9)(0, 0, 0)(11, 13, 14)6——(7, 8, 10)—(11, 13, 14)(0, 0, 0)Table 5
Energy/power capacity of each sensor node and rate of discharge of energy/power per unit time.
Sensor nodeVoltage/power capacity (%)Discharge of voltage/power per unit time (%)1(70, 72, 73)(2.0, 2.7, 3.0)2(65, 68, 70)(1.0, 1.6, 2.5)3(65, 69, 72)(4.5, 5.3, 6.0)4(64, 70, 75)(3.0, 3.6. 5.0)5(56, 62, 65)(2.0, 2.5, 3.5)6(75, 81, 84)(2.5, 3.3, 4.2)Using signed distance measureDt˜ij=Q˜i/q˜id˜ij,0˜ for sensor nodes i to j and the signed distance measure Dt˜ji=Q˜j/q˜jd˜ij′,0˜ for sensor nodes j to i the weight matrix DT˜0,0˜ has been presented in Table 6. The value infinity in the matrix DT˜0,0˜ indicates that there is no self-connectivity between the same sensor nodes. Now, to solve the proposed WSN problem mentioned in example 6, we have solved the same using the weight matrix given in Table 5 and the modified Floyd–Warshall’s algorithm in a fuzzy environment which has been described in Section 4.2. The modified Floyd–Warshall algorithm has been coded in C++ on the Linux operating system, and the results are reported in Table 7.Table 6
Weight matrixDT˜0,0˜.
Sensor node1234561∞2.98——1.70—24.37∞3.76———3—1.21∞——1.584———∞2.72-51.44——3.46∞1.836——2.93—1.89∞Table 7
All pair maximum connectivity matrixDT˜n,0˜.
Sensor node1234561—2.982.981.701.701.7024.37—3.761.701.701.7031.441.44—1.581.581.5841.441.441.83—2.721.8351.441.441.833.46—1.8361.441.442.931.891.89—According to the input in Table7, there is really no time to connect the same node since there is no self-connectivity between the same sensor nodes and therefore do not discharge voltage/power. Again, the output matrix is not symmetric here due to the different voltage/power of the sensor nodes. For example, the connection time between sensor nodes 1 and 2 is 2.98 but 2 and 1 is 4.37 as node 1 discharges more voltage than sensor node 2. Also, the connection between (node i to node j) and (node j to node i), i,j=1,2,3,4,5,6 are independent (see Chi-square test). The direct and intermediate time connectivity between any two nodes has also been present graphically. The time duration between source node 1 to 2 (direct connection) and other node’s intermediate connection has been presented in Figure 4. Similarly, the time duration between source nodes 2, 3, 4, 5, and 6 and their corresponding, direct, and intermediate connections are depicted in Figures 5–8, respectively. Furthermore, it is to be noted that the time complexity for solving the problem is On3 as we have computed all pair maximum connectivity for the entire WSN configurations under uncertain setup. However, it is stated explicitly that Sah et al. [16] have given a time-consuming technique (time complexity On2) to produce datasets for sensor node placement and packet creation.Figure 4
Connection time between source node 1 and nodej (j = 2, 3, 4, 5, 6).Figure 5
Connection time between source node 2 and nodej (j = 3, 4, 5, 6).Figure 6
Connection time between source node 3 and nodej (j = 4, 5, 6).Figure 7
Connection time between source node 4 and nodej (j = 5, 6).Figure 8
Connection time between source node 5 and nodej (j = 6).


### 6.1. Chi-Square Test

We have stated the hypothesis as follows:H0: connection between (node i to node j) and (node j to node i), i,j=1,2,3,4,5,6 are independentH1: connection between (node i to node j) and (node j to node i), i,j=1,2,3,4,5,6 are not independentLet the level of significantα=0.05 and X is a random variable having χ2 distribution. From Table 6, we have calculated p=ProbX>18.270=0.831 with 25 degrees of freedom (see Figure 9). As p>α=0.05, then we do not have enough evidence to reject the null hypothesis H0. Therefore, the connection between (i to j) and (j to i), i,j=1,2,3,4,5,6 are independent.Figure 9
χ2 distribution with 25 degrees of freedom.


## 6.1. Chi-Square Test

We have stated the hypothesis as follows:H0: connection between (node i to node j) and (node j to node i), i,j=1,2,3,4,5,6 are independentH1: connection between (node i to node j) and (node j to node i), i,j=1,2,3,4,5,6 are not independentLet the level of significantα=0.05 and X is a random variable having χ2 distribution. From Table 6, we have calculated p=ProbX>18.270=0.831 with 25 degrees of freedom (see Figure 9). As p>α=0.05, then we do not have enough evidence to reject the null hypothesis H0. Therefore, the connection between (i to j) and (j to i), i,j=1,2,3,4,5,6 are independent.Figure 9
χ2 distribution with 25 degrees of freedom.


## 7. Conclusions of this Study

For the first time, a modified version of the Floyd–Warshall’s Algorithm with imprecise parameters has been developed in this study to find the maximum connectivity time. This modified algorithm is a maximum time connectivity algorithm that can be applied to WSNs. The modified Floyd–Warshall algorithm has been written in C++ on the Linux platform. Because of the different voltage/power of the sensor nodes, the output matrix is not symmetric in this case. The maximum time connectivity among sensor nodes varies depending on the amount of voltage/power in each sensor node and the rate of discharge of voltage/power during the communication process. The proposed modified Floyd–Warshall algorithm has been discussed with a numerical example. The proposed algorithm discussed here is very simple and very easy to implement and to apply for solving other WSNs involving fuzzy parameters. The modified algorithm has been found to be useful for determining the maximum time duration linking in WSNs. It is also stated that the synchronization mode between sender and receiver nodes is extremely crucial for communicating in a WSN.


### 7.1. Future Scope of Research

The solution presented here is quite straightforward and simple to implement, and it can be stated that the overall process performed in this work will perform well enough to overcome numerous different WSN problems such as energy-efficient routing protocol for Wireless Sensor Networks, Sink Path Determination in Wireless Sensor Networks, Lifetime computation of WSN, dataset network-induced for wireless network networks, routing with deflections in WSNs.


## 7.1. Future Scope of Research

The solution presented here is quite straightforward and simple to implement, and it can be stated that the overall process performed in this work will perform well enough to overcome numerous different WSN problems such as energy-efficient routing protocol for Wireless Sensor Networks, Sink Path Determination in Wireless Sensor Networks, Lifetime computation of WSN, dataset network-induced for wireless network networks, routing with deflections in WSNs.



---

*Source: 5973433-2022-04-15.xml*