A distributed algorithm for hexagonal topology formation in wireless sensor networks

Hexagonal wireless sensor network refers to a network topology where a subset of nodes have six peer neighbors. These nodes form a backbone for multi-hop communications. In a previous work, we proposed the use of hexagonal topology in wireless sensor networks and discussed its properties in relation to real-time (bounded latency) multi-hop communications in large-scale deployments. In that work, we did not consider the problem of hexagonal topology formation in practice - which is the subject of this research. In this paper, we present a decentralized algorithm that forms the hexagonal topology backbone in an arbitrary but sufficiently dense network deployment. We implemented a prototype of our algorithm in NesC for TinyOS based platforms. We present data from field tests of our implementation, collected using a deployment of fifty wireless sensor nodes.

LLF schedulability analysis on multiprocessor platforms

LLF (Least Laxity First) scheduling, which assigns a higher priority to a task with smaller laxity, has been known as an optimal preemptive scheduling algorithm on a single processor platform. However, its characteristics upon multiprocessor platforms have been little studied until now. Orthogonally, it has remained open how to efficiently schedule general task systems, including constrained deadline task systems, upon multiprocessors. Recent studies have introduced zero laxity (ZL) policy, which assigns a higher priority to a task with zero laxity, as a promising scheduling approach for such systems (e.g., EDZL). Towards understanding the importance of laxity in multiprocessor scheduling, this paper investigates the characteristics of ZL policy and presents the first ZL schedulability test for any work-conserving scheduling algorithm that employs this policy. It then investigates the characteristics of LLF scheduling, which also employs the ZL policy, and derives the first LLF-specific schedulability test on multiprocessors. It is shown that the proposed LLF test dominates the ZL test as well as the state-of-art EDZL test.

Scheduling arbitrary-deadline sporadic task systems on multiprocessors

A new algorithm is proposed for scheduling preemptible arbitrary-deadline sporadic task systems upon multiprocessor platforms, with interprocessor migration permitted. This algorithm is based on a task-splitting approach - while most tasks are entirely assigned to specific processors, a few tasks (fewer than the number of processors) may be split across two processors. This algorithm can be used for two distinct purposes: for actually scheduling specific sporadic task systems, and for feasibility analysis. Simulation- based evaluation indicates that this algorithm offers a significant improvement on the ability to schedule arbitrary- deadline sporadic task systems as compared to the contemporary state-of-art. With regard to feasibility analysis, the new algorithm is proved to offer superior performance guarantees in comparison to prior feasibility tests.

On the development of a test-bed application for the ART-WiSe architecture

The ART-WiSe (Architecture for Real-Time communications in Wireless Sensor Networks) framework aims at the design of new communication architectures and mechanisms for time-sensitive Wireless Sensor Networks (WSNs). We adopted a two-tiered architecture where an overlay Wireless Local Area Network (Tier 2) serves as a backbone for a WSN (Tier 1), relying on existing standard communication protocols and commercial-off-the-shell (COTS) technologies – IEEE 802.15.4/ZigBee for Tier 1 and IEEE 802.11 for Tier 2. In this line, a test-bed application is being developed for assessing, validating and demonstrating the ART-WiSe architecture. A pursuit-evasion application was chosen since it fulfils a number of requirements, namely it is feasible and appealing and imposes some stress to the architecture in terms of timeliness. To develop the testbed based on the previously referred technologies, an implementation of the IEEE 8021.5.4/ZigBee protocols is being carried out, since there is no open source available to the community. This paper highlights some relevant aspects of the ART-WiSe architecture, provides some intuition on the protocol stack implementation and presents a general view over the envisaged test-bed application.

On a test-bed application for the ART-WiSe framework

This report describes the development of a Test-bed Application for the ART-WiSe Framework with the aim of providing a means of access, validate and demonstrate that architecture. The chosen application is a kind of pursuit-evasion game where a remote controlled robot, navigating through an area covered by wireless sensor network (WSN), is detected and continuously tracked by the WSN. Then a centralized control station takes the appropriate actions for a pursuit robot to chase and “capture” the intruder one. This kind of application imposes stringent timing requirements to the underlying communication infrastructure. It also involves interesting research problems in WSNs like tracking, localization, cooperation between nodes, energy concerns and mobility. Additionally, it can be easily ported into a real-world application. Surveillance or search and rescue operations are two examples where this kind of functionality can be applied. This is still a first approach on the test-bed application and this development effort will be continuously pushed forward until all the envisaged objectives for the Art-WiSe architecture become accomplished.

Neighbour list optimization for real LTE radio network

With the increasing complexity of current networks, it became evident the need for Self-Organizing Networks (SON), which aims to automate most of the associated radio planning and optimization tasks. Within SON, this paper aims to optimize the Neighbour Cell List (NCL) for Long Term Evolution (LTE) evolved NodeBs (eNBs). An algorithm composed by three decisions were were developed: distance-based, Radio Frequency (RF) measurement-based and Handover (HO) stats-based. The distance-based decision, proposes a new NCL taking account the eNB location and interference tiers, based in the quadrants method. The last two algorithms consider signal strength measurements and HO statistics, respectively; they also define a ranking to each eNB and neighbour relation addition/removal based on user defined constraints. The algorithms were developed and implemented over an already existent radio network optimization professional tool. Several case studies were produced using real data from a Portuguese LTE mobile operator. © 2014 IEEE.

Practical simulation of GNSS signals in the presence of ionospheric scintillaton

We propose a low complexity technique to generate amplitude correlated time-series with Nakagami-m distribution and phase correlated Gaussian-distributed time-series, which is useful in the simulation of ionospheric scintillation effects during the transmission of GNSS signals. The method requires only the knowledge of parameters S4 (scintillation index) and σΦ (phase standard deviation) besides the definition of models for the amplitude and phase power spectra. The Zhang algorithm is used to produce Nakagami-distributed signals from a set of Gaussian autoregressive processes.

A hybrid genetic algorithm for the multi-mode resource-constrained project scheduling

A construction project is a group of discernible tasks or activities that are conduct-ed in a coordinated effort to accomplish one or more objectives. Construction projects re-quire varying levels of cost, time and other resources. To plan and schedule a construction project, activities must be defined sufficiently. The level of detail determines the number of activities contained within the project plan and schedule. So, finding feasible schedules which efficiently use scarce resources is a challenging task within project management. In this context, the well-known Resource Constrained Project Scheduling Problem (RCPSP) has been studied during the last decades. In the RCPSP the activities of a project have to be scheduled such that the makespan of the project is minimized. So, the technological precedence constraints have to be observed as well as limitations of the renewable resources required to accomplish the activities. Once started, an activity may not be interrupted. This problem has been extended to a more realistic model, the multi-mode resource con-strained project scheduling problem (MRCPSP), where each activity can be performed in one out of several modes. Each mode of an activity represents an alternative way of combining different levels of resource requirements with a related duration. Each renewable resource has a limited availability for the entire project such as manpower and machines. This paper presents a hybrid genetic algorithm for the multi-mode resource-constrained pro-ject scheduling problem, in which multiple execution modes are available for each of the ac-tivities of the project. The objective function is the minimization of the construction project completion time. To solve the problem, is applied a two-level genetic algorithm, which makes use of two separate levels and extend the parameterized schedule generation scheme. It is evaluated the quality of the schedules and presents detailed comparative computational re-sults for the MRCPSP, which reveal that this approach is a competitive algorithm.

A genetic algorithm for the resource constrained multi-project scheduling problem

This paper presents a genetic algorithm for the resource constrained multi-project scheduling problem. The chromosome representation of the problem is based on random keys. The schedules are constructed using a heuristic that builds parameterized active schedules based on priorities, delay times, and release dates defined by the genetic algorithm. The approach is tested on a set of randomly generated problems. The computational results validate the effectiveness of the proposed algorithm.

Analysis of the domain of applicability of an algorithm for a resources system selection problem for Distributed/Agile/Virtual Enterprises integration

The process of resources systems selection takes an important part in Distributed/Agile/Virtual Enterprises (D/A/V Es) integration. However, the resources systems selection is still a difficult matter to solve in a D/A/VE, as it is pointed out in this paper. Globally, we can say that the selection problem has been equated from different aspects, originating different kinds of models/algorithms to solve it. In order to assist the development of a web prototype tool (broker tool), intelligent and flexible, that integrates all the selection model activities and tools, and with the capacity to adequate to each D/A/V E project or instance (this is the major goal of our final project), we intend in this paper to show: a formulation of a kind of resources selection problem and the limitations of the algorithms proposed to solve it. We formulate a particular case of the problem as an integer programming, which is solved using simplex and branch and bound algorithms, and identify their performance limitations (in terms of processing time) based on simulation results. These limitations depend on the number of processing tasks and on the number of pre-selected resources per processing tasks, defining the domain of applicability of the algorithms for the problem studied. The limitations detected open the necessity of the application of other kind of algorithms (approximate solution algorithms) outside the domain of applicability founded for the algorithms simulated. However, for a broker tool it is very important the knowledge of algorithms limitations, in order to, based on problem features, develop and select the most suitable algorithm that guarantees a good performance.

Single-objective spreading algorithm

This paper addresses the problem of finding several different solutions with the same optimum performance in single objective real-world engineering problems. In this paper a parallel robot design is proposed. Thereby, this paper presents a genetic algorithm to optimize uni-objective problems with an infinite number of optimal solutions. The algorithm uses the maximin concept and ε-dominance to promote diversity over the admissible space. The performance of the proposed algorithm is analyzed with three well-known test functions and a function obtained from practical real-world engineering optimization problems. A spreading analysis is performed showing that the solutions drawn by the algorithm are well dispersed.

Logarithmically proportional objective function for planar surfaces recognition in 3D point cloud

3D laser scanning is becoming a standard technology to generate building models of a facility's as-is condition. Since most constructions are constructed upon planar surfaces, recognition of them paves the way for automation of generating building models. This paper introduces a new logarithmically proportional objective function that can be used in both heuristic and metaheuristic (MH) algorithms to discover planar surfaces in a point cloud without exploiting any prior knowledge about those surfaces. It can also adopt itself to the structural density of a scanned construction. In this paper, a metaheuristic method, genetic algorithm (GA), is used to test this introduced objective function on a synthetic point cloud. The results obtained show the proposed method is capable to find all plane configurations of planar surfaces (with a wide variety of sizes) in the point cloud with a minor distance to the actual configurations. © 2014 IEEE.

A genetic algorithm for project scheduling with multi-modes and renewable resources

This paper presents a genetic algorithm-based approach for project scheduling with multi-modes and renewable resources. In this problem activities of the project may be executed in more than one operating mode and renewable resource constraints are imposed. The objective function is the minimization of the project completion time. The idea of this approach is integrating a genetic algorithm with a schedule generation scheme. This study also proposes applying a local search procedure trying to yield a better solution when the genetic algorithm and the schedule generation scheme obtain a solution. The experimental results show that this algorithm is an effective method for solving this problem.

Project scheduling under multiple resources constraints using a genetic algorithm

The resource constrained project scheduling problem (RCPSP) is a difficult problem in combinatorial optimization for which extensive investigation has been devoted to the development of efficient algorithms. During the last couple of years many heuristic procedures have been developed for this problem, but still these procedures often fail in finding near-optimal solutions. This paper proposes a genetic algorithm for the resource constrained project scheduling problem. The chromosome representation of the problem is based on random keys. The schedule is constructed using a heuristic priority rule in which the priorities and delay times of the activities are defined by the genetic algorithm. The approach was tested on a set of standard problems taken from the literature and compared with other approaches. The computational results validate the effectiveness of the proposed algorithm.

Project scheduling using a competitive genetic algorithm

- The resource constrained project scheduling problem (RCPSP) is a difficult problem in combinatorial optimization for which extensive investigation has been devoted to the development of efficient algorithms. During the last couple of years many heuristic procedures have been developed for this problem, but still these procedures often fail in finding near-optimal solutions. This paper proposes a genetic algorithm for the resource constrained project scheduling problem. The chromosome representation of the problem is based on random keys. The schedule is constructed using a heuristic priority rule in which the priorities and delay times of the activities are defined by the genetic algorithm. The approach was tested on a set of standard problems taken from the literature and compared with other approaches. The computational results validate the effectiveness of the proposed algorithm