A Heuristic Algorithm is a problem-solving approach or methodology that uses practical and intuitive strategies to find approximate solutions to optimization or decision-making problems. Unlike exact algorithms that guarantee optimal solutions, heuristics focus on quickly finding reasonably good solutions, especially in situations where finding an exact solution is computationally challenging or impractical.

Posts

Availability Analysis for Reliable Distributed Fiber Optic Sensors Placement

We perform the availability analysis for various reliable distributed fiber optic sensor placement schemes in the circumstances of multiple failures. The study can help the network carriers to select the optimal protection scheme for their network sensing services, considering both service availability and hardware cost.

Distributed Fiber Optic Sensors Placement for Infrastructure-as-a-Sensor

Recently, the distributed fiber optic sensing (DFOS) techniques have advanced rapidly. There emerges various types of DFOS sensors that can monitor physical parameters such as temperature, strain, and vibration. With these DFOS sensors deployed, the telecom networks are capable of offering additional services beyond communications, such as monitoring road traffic condition, monitoring utility pole health, monitoring city noise and accident, thus evolving to a new paradigm of Infrastructure-as-a-Sensor (IaaSr) or Network-as-a-Sensor (NaaSr). When telecom network carriers upgrade their infrastructures with DFOS sensors to provide such IaaSr/NaaSr services, there will arise a series of critical challenges: (1) where to place the DFOS sensors, and (2) how to provision the DFOS sensing fiber routes to cover the whole network infrastructures with the minimum number of DFOS sensors? We name this as the DFOS placement problem. In this paper, we prove that the DFOS placement problem is an NP-hard problem, and we analyze the upper bound of the number of DFOS sensors used. To facilitate the optimal solution, we formulate the DFOS placement problem with an Integer Linear Programming model that aims at minimizing the number of DFOS sensors used. Furthermore, we propose a cost-efficient heuristic solution, called Explore-and-Pick (EnP), which can achieve a close-to-optimal performance in a fast manner. We analyze the approximation ratio and the computational complexity of the proposed EnP algorithm. In addition, we conduct comprehensive simulations to evaluate the performance of the proposed solutions. Simulation results show that the EnP algorithm can outperform the baseline algorithm by 16% in average and 26% at best, and it achieves a performance that is close to the optimal result obtained by ILP.

An Efficient Approach for Placing Distributed Fiber Optic Sensors with Concurrent Sensing Capability

We propose an efficient approach for placing distributed fiber optic sensors (DFOS) with concurrent sensing capability. It consumes 5.7% to 9.5% fewer sensors than that using DFOS without concurrent sensing, for covering the same network.

Address Challenges in Placing Distributed Fiber Optic Sensors

We are the first to investigate a novel problem, called distributed fiber optic sensor placement, in the context of Infrastructure-as-a-Sensor. We propose an ILP-based optimal solution and a close-to-optimal heuristic solution, both of which aim at minimizing the cost of sensors.