Research
Research Summary
My research focuses on the applications of optimization techniques (e.g., linear programming, mixed-integer programming, heuristics, etc.) for modeling and analyzing research problems on wireless communications and networks. More specifically,
Ad Hoc Networks,
Wireless Sensor Networks,
Underwater Acoustic Sensor Networks,
Internet of Things,
Smart Grids,
are my favorite research areas.
Maximization of Wireless Sensor Networks Lifetime via Linear Programming
Wireless Sensor Networks (WSNs) are proven to be an emerging technology for the Internet of Things. A typical WSN is composed of numerous battery-limited sensor nodes and a central sink node (base station). Sensor nodes periodically capture data about the environment and transfer the collected data to the sink node either by using direct or multi-hop communication techniques for further processing. An example of a two-dimensional WSN is provided in Figure 1(a). In this figure, the network has a disk shape where the sensor nodes are randomly deployed within the disk. The sink node is located at the center of the disk. Although disk-shaped WSNs are particularly popular in the literature, linear or grid topologies are two other favorite network topologies. Battery-operated sensor nodes are randomly deployed in hostile areas; hence, changing the battery of the sensor nodes is infeasible. Moreover, nodes near the sink node have a high traffic burden since these nodes need to relay other nodes' data. Considering these challenges, prolonging the operational lifetime of WSNs is of the utmost importance.
Underwater WSNs have a similar role as terrestrial WSNs. However, the underwater WSN nodes are generally deployed in a three-dimensional area depicted in Figure 1(b). In this figure, the network has a rectangular prism shape. Three sink nodes (sonobuoys) are positioned on the water's surface. Sensor nodes have different depths in water, and these nodes are randomly deployed within the rectangular region.
The main differences between the terrestrial and the underwater WSNs are summarized as follows.
In terrestrial WSNs, electromagnetic waves are used for communication, while in underwater WSNs, acoustic communication is preferred since electromagnetic waves are absorbed in water quickly.
Underwater sensor nodes may not be static as in terrestrial WSNs since waves can change the position of the nodes.
Underwater acoustic communication has harsh channel characteristics (e.g., high packet drop ratio, long propagation delay, low bandwidth, etc.)
Underwater sensor nodes consume excessive energy for transmission. Prolonging the network lifetime should also be considered a critical goal for underwater WSNs.
Terrestrial or underwater WSNs lifetime can be maximized using the linear programming (LP) technique [1]. LP is an optimization technique used to maximize or minimize a linear objective function under a set of linear constraints. More detail on the LP is given in [2].
Figure 1(a) — Terrestrial WSN Topology
Figure 1(b) — Underwater WSN Topology
A simple LP model to maximize the WSNs lifetime is presented in Figure 2. For this LP model, the WSN has a single sink node (denoted by node-1) and N sensor nodes (node-2 to node-(N+1)). The network topology can be in any shape, such as disk, linear, grid, etc.
Sensor nodes have the initial battery energy of E (in Joules), and the sink node does not have a battery constraint as the sensor nodes. Each sensor node-i generates s_i number of bits per unit time. A constant bit rate traffic is adopted. The sink node cannot generate data; hence, a many-to-one traffic pattern in the network (i.e., all the data generated by the sensor nodes are collected at the sink node) is achieved.
Figure 2 — The LP Model for Maximizing the Lifetime of WSNs
The objective function of the LP model is the maximization of WSN lifetime (t), the time until the first node dies, which is a widely adopted definition of the network lifetime. The decision variables of this LP model are
f_{ij}: The number of bits transmitted from node-i to node-j during the network lifetime,
e_i: The total energy consumed by sensor node-i during the network lifetime (in Joules).
The constraints of the LP model are presented in (1)-(5).
Constraint (1) ensures flow balancing at each sensor node-i. This constraint equates the number of outgoing bits from node-i minus the incoming bits to node-i to the total number of bits generated by each sensor node-i (i.e., s_i * t).
Constraint (2) calculates the total amount of energy consumed by node-i (i.e., e_i) during the network lifetime. In this constraint, the parameters, E_{tx,ij} and E_{rx} are the energy costs for transmitting and receiving a single bit, respectively. E_{tx,ij} and E_{rx} parameters are calculated using Equations (6) and (7), respectively [3]. In these equations, E_{elec} denotes the electronics energy, E_{amp} is determined by the transmitter amplifier’s efficiency, a is the path loss exponent (which is typically taken as 2), and d_{ij} is the distance between node-i and node-j (in meters).
Constraint (3) limits the total amount of energy consumed by node-i (i.e., e_i) during the network lifetime to the initial battery energy of the sensor nodes (E).
Constraints (4) and (5) are the non-negativity constraints (in other words, the boundaries) for the decision variables.
The LP model in Figure 2 can be developed and solved using General Algebraic Modeling System (GAMS). GAMS is a high-level modeling system for modeling and solving mathematical optimization problems. GAMS contains an integrated development environment (IDE), and it is connected to several third-party optimization solvers such as CPLEX, XPRESS, etc. GAMS can also be interfaced with MATLAB. Interfacing GAMS and MATLAB is achieved via GDXMRW (GDX-Matlab Read/Write), a suite of utilities to exchange data between GAMS and MATLAB. The videos given below show how to interface GAMS and MATLAB. For further reading, please refer to this link.
The GAMS and MATLAB scripts for the WSN lifetime maximization problem are provided in the Google Drive folder. The process cycle for the WSN lifetime maximization problem is provided in Figure 3. The details for the process cycle are itemized as follows:
The main.m script should be compiled first. This script first initializes the parameters (i.e., N, s_i, E, E_{elec}, and E_{amp}). Then, it randomly generates a disk topology with the radius Rnet meters. Finally, the script calculates the energy parameters, (i.e., E_{tx,ij} and E_{rx}).
main.m calls the trrun.m script that writes the GDX file, inputGDX.gdx. This GDX file contains the necessary information on the parameters for solving the LP model. Then, trrun.m calls the GAMS model file (i.e., model.gms).
The GAMS script, model.gms, contains the objective function and the constraints of the LP model. When GAMS solves the LP model to optimality, the optimal solutions of the LP model (i.e., t, f_{ij}, and e_i) are written in the outputGDX.gdx file.
trrun.m reads the outputGDX.gdx file for getting the optimal solutions, which are used for post-processing in the main.m script.
The LP model is solved to optimality using the GAMS/MATLAB script provided above. For visuality, the network topology is assumed to be linear, where four sensor nodes and a single sink node are positioned as illustrated in Figure 4. The distance between the adjacent nodes is 100 meters. Node-1 is marked as the sink node, while nodes 2-5 are the ordinary sensor nodes. The parameters used for solving the LP model are listed in Table 1.
Figure 4 presents the optimal flows for maximizing the WSN lifetime. The network lifetime is obtained as t=275099 seconds (3.18 days). According to Table 1, each sensor node-i is assumed to generate 1 bit per second (i.e., s_i=1). Hence, each sensor node-i generates a total of 275099 bits (34.39 KB) during the network lifetime. Node-5 (the farthest node to the sink node) transmits 227690 bits (28.46 KB) to node-4 (i.e., f_{54}=227690), while it transmits 47409 bits (5.93 KB) to the sink node (i.e., f_{51}=47409). In other words, node-5 transmits 83% of its generated data to its nearest node (i.e., node-4), while it transmits 17% of its generated data "directly" to the sink node.
Nodes 2-4 are acting as relay nodes such that they transmit their generated data to the sink node while carrying other nodes' data. For example, node-4 receives 227690 bits (28.46 KB) from node-5, while it generates 275099 bits (34.39 KB) during the network lifetime. Moreover, node-4 transmits 445204 bits (55.65 KB) and 57585 bits (7.20 KB) to node-3 and node-1, respectively. Hence, the total number of bits flowing out of node-4 is calculated as 445204+57585=502789 bits, 62.85 KB (i.e., f_{43}+f_{41}=502789). On the other hand, the incoming flow for node-4 is 227690 bits (i.e., f_{54}=227690). Thus, the total number of bits generated by node-4 is 502789-227690=275099 bits (according to the Constraint (1) in Figure 2), which is the amount of data that node-4 generates during the network lifetime. The sink node collects all the data generated by the sensor nodes, and the sink node does not generate data. The total incoming flow for the sink node is calculated as 57585+921595+73807+47409=1100396 bits (137.55 KB), which is the total number of bits generated by all the sensor nodes during the network lifetime (i.e., 4x275099=1100396 bits).
In Figure 5, the total energy consumed of each node is presented. Note that all sensor nodes dissipate all of their initial battery energies (1 J according to Table 1) nearly at the same time. More specifically, all sensor nodes dissipate at least 99.999% of their initial battery energies until the network dies. The optimal solution of the LP model shows that the LP-based WSN lifetime maximization technique is proven to prevent any premature death of sensor nodes for maximizing the WSNs lifetime.
Figure 4 — Optimal Flows
Figure 5 — Total Energy Consumed by Each Node (e_i)
Table 1 — List of Parameters Used in the Analysis
References
[1] Ergen, S. C., & Varaiya, P. (2005). On multi-hop routing for energy efficiency. IEEE Communications Letters, 9(10), 880-881.
[2] Chinneck, J. W. (2006). Practical Optimization: A Gentle Introduction. Systems and Computer Engineering, Carleton University, Ottawa.
[3] Cheng, Z., Perillo, M., & Heinzelman, W. B. (2008). General network lifetime and cost models for evaluating sensor network deployment strategies. IEEE Transactions on Mobile Computing, 7(4), 484-497.
Tutorial Documents and Videos
The document titled "Underwater Channel and Energy Models" provides a brief introduction to the channel and energy models that are used in underwater WSNs.
The document titled "A GAMS Tutorial" gives a brief tutorial on using GAMS.
"GAMS Lessons" YouTube channel contains videos featuring GAMS.
Underwater Basics.pdfUnderwater Channel and Energy Models
A brief tutorial on underwater sensor networks, channel/energy models, and optimization frameworks.
A GAMS Tutorial.pdfA GAMS Tutorial
A brief tutorial on General Algebraic Modeling System (GAMS).