Search results

1 – 10 of 260
To view the access options for this content please click here
Article
Publication date: 20 November 2009

Kai Chen and Klara Nahrstedt

Group communication has become increasing important in mobile ad hoc networks (MANET). Current multicast routing protocols in MANET have been shown to incur large…

Abstract

Purpose

Group communication has become increasing important in mobile ad hoc networks (MANET). Current multicast routing protocols in MANET have been shown to incur large overheads due to dynamic network topology. To this end, this paper proposes an overlay multicast scheme in MANET that is more efficient.

Design/methodology/approach

The approach is to construct an overlay multicast tree based on the locations of the group nodes. The paper proposes several tree construction algorithms, namely, location‐guided k‐ary (LGK) tree, location‐guided directional (LGD) tree and location‐guided Steiner (LGS) tree. All of them rely on the geometric locations of the nodes as heuristics to construct the tree. The paper also introduces several mechanisms to enhance the proposed algorithms.

Findings

The simulation results show that the location‐guided heuristics is very effective in constructing low bandwidth cost overlay multicast trees in MANET. When location information is up‐to‐date, the bandwidth cost of a LGS tree is similar to that of an optimal router‐assisted Steiner multicast tree. When location information is out‐dated, LGD tree has the lowest cost.

Originality/value

This paper demonstrates the effectiveness of location‐guided heuristics in constructing overlay multicast trees in MANET. This study strongly suggests that location‐guided heuristics can be used to design many other algorithms in a mobile network.

Details

International Journal of Pervasive Computing and Communications, vol. 5 no. 4
Type: Research Article
ISSN: 1742-7371

Keywords

To view the access options for this content please click here
Article
Publication date: 27 September 2011

Qiang Liu and Chengen Wang

The purpose of this paper is to develop a new rectilinear branch pipe‐routing algorithm for automatic generation of rectilinear branch pipe routes in constrained spaces of…

Abstract

Purpose

The purpose of this paper is to develop a new rectilinear branch pipe‐routing algorithm for automatic generation of rectilinear branch pipe routes in constrained spaces of aero‐engines.

Design/methodology/approach

Rectilinear branch pipe routing that connects multiple terminals in a constrained space with obstacles can be formulated as a rectilinear Steiner minimum tree with obstacles (RSMTO) problem while meeting certain engineering rules, which has been proved to be an NP‐hard and discrete problem. This paper presents a discrete particle swarm optimization (PSO) algorithm for rectilinear branch pipe routing (DPSO‐RBPRA) problems, which adopts an attraction operator and an energy function to plan the shortest collision‐free connecting networks in a discrete graph space. Moreover, this paper integrates several existing techniques to evaluate particles for the RSMTO problem in discrete Manhattan spaces. Further, the DPSO‐RBPRA is extended to surface cases to adapt to requirements of routing pipes on the surfaces of aero‐engines.

Findings

Pipe routing numeral computations show that, DPSO‐RBPRA finds satisfactory connecting networks while considering several engineering rules, which demonstrates the effectiveness of the proposed method.

Originality/value

This paper applies the Steiner tree theory and develops a DPSO algorithm to plan the aero‐engine rectilinear branch pipe‐routing layouts.

To view the access options for this content please click here
Article
Publication date: 7 August 2019

Nadjib Benaouda and Ammar Lahlouhi

The purpose of this paper is to present a novel delay-bounded and power-efficient routing for in-network data aggregation, called DPIDA, which aims to ensure a compromise…

Abstract

Purpose

The purpose of this paper is to present a novel delay-bounded and power-efficient routing for in-network data aggregation, called DPIDA, which aims to ensure a compromise between the energy consumed during the collection of data sensed by a set of source sensor nodes and their timely delivery to the sink node.

Design/methodology/approach

Based on the ant-colony-optimization metaheuristic, the proposal establishes a routing structure that maximizes the number of overlapping routes and minimizes the total transmission power while ensuring delay-bounded paths and a symmetric transmission power assignment to reliably deliver the sensed data.

Findings

The proposal was extensively compared to two other known protocols regarding different keys factors. Simulation results, including topology snapshots, show the ability of DPIDA to ensure the energy–latency tradeoff. They also show the superiority of DPIDA compared to the two considered protocols.

Originality/value

This paper presents a novel ant-based protocol that uses in-network data aggregation and transmission power-adjustment techniques to conserve the energy of nodes while ensuring delay-bounded paths and a reliable deliverance of data which is ensured by providing a symmetric transmission power assignment.

Details

International Journal of Pervasive Computing and Communications, vol. 15 no. 2
Type: Research Article
ISSN: 1742-7371

Keywords

To view the access options for this content please click here
Article
Publication date: 14 April 2014

Chang-Sup Park and Sungchae Lim

The paper aims to propose an effective method to process keyword-based queries over graph-structured databases which are widely used in various applications such as XML…

Abstract

Purpose

The paper aims to propose an effective method to process keyword-based queries over graph-structured databases which are widely used in various applications such as XML, semantic web, and social network services. To satisfy users' information need, it proposes an extended answer structure for keyword queries, inverted list indexes on keywords and nodes, and query processing algorithms exploiting the inverted lists. The study aims to provide more effective and relevant answers to a given query than the previous approaches in an efficient way.

Design/methodology/approach

A new relevance measure for nodes to a given keyword query is defined in the paper and according to the relevance metric, a new answer tree structure is proposed which has no constraint on the number of keyword nodes chosen for each query keyword. For efficient query processing, an inverted list-style index is suggested which pre-computes connectivity and relevance information on the nodes in the graph. Then, a query processing algorithm based on the pre-constructed inverted lists is designed, which aggregates list entries for each graph node relevant to given keywords and identifies top-k root nodes of answer trees most relevant to the given query. The basic search method is also enhanced by using extend inverted lists which store additional relevance information of the related entries in the lists in order to estimate the relevance score of a node more closely and to find top-k answers more efficiently.

Findings

Experiments with real datasets and various test queries were conducted for evaluating effectiveness and performance of the proposed methods in comparison with one of the previous approaches. The experimental results show that the proposed methods with an extended answer structure produce more effective top-k results than the compared previous method for most of the queries, especially for those with OR semantics. An extended inverted list and enhanced search algorithm are shown to achieve much improvement on the execution performance compared to the basic search method.

Originality/value

This paper proposes a new extended answer structure and query processing scheme for keyword queries on graph databases which can satisfy the users' information need represented by a keyword set having various semantics.

Details

International Journal of Web Information Systems, vol. 10 no. 1
Type: Research Article
ISSN: 1744-0084

Keywords

To view the access options for this content please click here
Article
Publication date: 23 January 2009

Andrzej Kos and Zbigniew Nagórny

The aim of this work is to examine the Hopfield network for the field programmable gate array (FPGA) cell placement.

Abstract

Purpose

The aim of this work is to examine the Hopfield network for the field programmable gate array (FPGA) cell placement.

Design/methodology/approach

Implementation of an algorithm in FPGA circuits requires synthesis, placement and the routing of logic cells. The placement takes the longest time for computation. Therefore, an algorithm for a run‐time reconfigurable system can be chosen from among earlier prepared algorithms. This paper presents a Hopfield neural network for solving the placement problem. The Hopfield network was also used for processing units in a parallel placement. Hardware implementation of presented solutions could accelerate the FPGA placement by orders of magnitude in comparison with placers executed on traditional computers. Hardware accelerators could also be applied to the design of other VLSI circuits. The simulation results for the FPGA placement are presented.

Findings

The Hopfield network and parallel placement give comparable placements with the method using a simulated annealing algorithm. The parallel placement enables a decrease in total number of neurons and neuron connections which are necessary for simultaneous placement of all cells in a circuit.

Research limitations/implications

This work provides a starting‐point for further research under hardware realization of the cell placement by using the Hopfield network. The presented solutions can be used for FPGA, gate array, sea‐of‐gates circuits and standard cell circuits with the same size cells.

Originality/value

The Hopfield network is used for placement in real circuits, in which nets contain multiple terminals, and for processing units in a parallel placement.

Details

Microelectronics International, vol. 26 no. 1
Type: Research Article
ISSN: 1356-5362

Keywords

To view the access options for this content please click here
Article
Publication date: 20 August 2018

Chang-Sup Park

This paper aims to propose a new keyword search method on graph data to improve the relevance of search results and reduce duplication of content nodes in the answer trees

Abstract

Purpose

This paper aims to propose a new keyword search method on graph data to improve the relevance of search results and reduce duplication of content nodes in the answer trees obtained by previous approaches based on distinct root semantics. The previous approaches are restricted to find answer trees having different root nodes and thus often generate a result consisting of answer trees with low relevance to the query or duplicate content nodes. The method allows limited redundancy in the root nodes of top-k answer trees to produce more effective query results.

Design/methodology/approach

A measure for redundancy in a set of answer trees regarding their root nodes is defined, and according to the metric, a set of answer trees with limited root redundancy is proposed for the result of a keyword query on graph data. For efficient query processing, an index on the useful paths in the graph using inverted lists and a hash map is suggested. Then, based on the path index, a top-k query processing algorithm is presented to find most relevant and diverse answer trees given a maximum amount of root redundancy allowed for a set of answer trees.

Findings

The results of experiments using real graph datasets show that the proposed approach can produce effective query answers which are more diverse in the content nodes and more relevant to the query than the previous approach based on distinct root semantics.

Originality/value

This paper first takes redundancy in the root nodes of answer trees into account to improve the relevance and content nodes redundancy of query results over the previous distinct root semantics. It can satisfy the users’ various information need on a large and complex graph data using a keyword-based query.

Details

International Journal of Web Information Systems, vol. 14 no. 3
Type: Research Article
ISSN: 1744-0084

Keywords

To view the access options for this content please click here
Article
Publication date: 4 March 2016

YEISON JULIAN CAMARGO, Leonardo Juan Ramirez and Ana Karina Martinez

The current work shows an approach to solve the QoS multicast routing problem by using Particle Swarm Optimization (PSO).The problem of finding a route from a source node…

Abstract

Purpose

The current work shows an approach to solve the QoS multicast routing problem by using Particle Swarm Optimization (PSO). The problem of finding a route from a source node to multiple destination nodes (multicast) at a minimum cost is an NP-Complete problem (Steiner tree problem) and is even greater if Quality of Service -QoS- constraints are taken into account. Thus, approximation algorithms are necessary to solve this problem. This work presents a routing algorithm with two QoS constraints (delay and delay variation) for solving the routing problem based on a modified version of particle swarm optimization.

Design/methodology/approach

This work involved the following methodology: 1. Literature Review 2. Routing algorithm design 3. Implementation of the designed routing algorithm by java programming. 4. Simulations and results.

Findings

In this work we compared our routing algorithm against the exhaustive search approach. The results showed that our algorithm improves the execution times in about 40% with different topologies.

Research limitations/implications

The algorithm was tested in three different topologies with 30, 40 and 50 nodes with and a dense graph topology.

Originality/value

Our algorithm implements a novel technique for fine tuning the parameters of the implemented bio-inspired model (Particles Swarm Optimization) by using a Genetic Meta-Optimizer. We also present a simple and multi implementation approach by using an encoding system that fits multiple bio-inspired models.

Details

Engineering Computations, vol. 33 no. 2
Type: Research Article
ISSN: 0264-4401

To view the access options for this content please click here
Article
Publication date: 1 November 2005

Qinglan Li, Jonathan Beaver, Ahmed Amer, Panos K. Chrysanthis, Alexandros Labrinidis and Ganesh Santhanakrishnan

Wireless sensor networks are expected to be an integral part of any pervasive computing environment. This implies an ever‐increasing need for efficient energy and resource…

Abstract

Wireless sensor networks are expected to be an integral part of any pervasive computing environment. This implies an ever‐increasing need for efficient energy and resource management of both the sensor nodes, as well as the overall sensor network, in order to meet the expected quality of data and service requirements. There have been numerous studies that have looked at the routing of data in sensor networks with the sole intention of reducing communication power consumption. However, there has been comparatively little prior art in the area of multi‐criteria based routing that exploit both the semantics of queries and the state of sensor nodes to improve network service longevity. In this paper, we look at routing in sensor networks from this perspective and propose an adaptive multi‐criteria routing protocol. Our algorithm offers automated reconfiguration of the routing tree as demanded by variations in the network state to meet application service requirements. Our experimental results show that our approach consistently outperforms, in terms of Network Lifetime and Coverage, the leading semantic‐based routing algorithm which reconfigures the routing tree at fixed periods.

Details

International Journal of Pervasive Computing and Communications, vol. 1 no. 4
Type: Research Article
ISSN: 1742-7371

Keywords

To view the access options for this content please click here
Article
Publication date: 28 July 2021

Tsz-Ho Kwok

Support structures are often needed in additive manufacturing (AM) to print overhangs. However, they are the extra materials that must be removed afterwards. When the…

Abstract

Purpose

Support structures are often needed in additive manufacturing (AM) to print overhangs. However, they are the extra materials that must be removed afterwards. When the supports have many contacts to the model or are even enclosed inside some concavities, removing them is very challenging and has a risk of damaging the part. Therefore, the purpose of this paper is to develop a new type of tree-support, named Escaping Tree-Support (ET-Sup), which tries to build all the supports onto the build plate to minimize the number of contact points.

Design/methodology/approach

The methodology is to first classify the support points into three categories: clear, obstructed and enclosed. A clear point has nothing between it and the build plate; an obstructed point is not clear, but there exists a path for it to reach the build plate; and an enclosed point has no way to reach the build plate. With this classification, the path for the obstructed points to come clear can be found through linking them to the clear points. All the operations are performed efficiently with the help of a ray representation.

Findings

The method is tested on different overhang features, including a lattice ball and a mushroom shape with a concave cap. All the supports generated for the examples can find their way to the build plate, which looks like they are escaping from the model. The computation time is around one second for these cases.

Originality/value

This is the first time truly realizing this “escaping” property in the generation of tree-like support structures. With this ET-Sup, it is expected that the AM industries can reduce the manufacturing lead time and save much labor work in post-processing.

Details

Rapid Prototyping Journal, vol. ahead-of-print no. ahead-of-print
Type: Research Article
ISSN: 1355-2546

Keywords

To view the access options for this content please click here
Article
Publication date: 12 March 2018

Wenhong Wei, Yong Qin and Zhaoquan Cai

The purpose of this paper is to propose a multi-objective differential evolution algorithm named as MOMR-DE to resolve multicast routing problem. In mobile ad hoc network…

Abstract

Purpose

The purpose of this paper is to propose a multi-objective differential evolution algorithm named as MOMR-DE to resolve multicast routing problem. In mobile ad hoc network (MANET), multicast routing is a non-deterministic polynomial -complete problem that deals with the various objectives and constraints. Quality of service (QoS) in the multicast routing problem mainly depends on cost, delay, jitter and bandwidth. So the cost, delay, jitter and bandwidth are always considered as multi-objective for designing multicast routing protocols. However, mobile node battery energy is finite and the network lifetime depends on node battery energy. If the battery power consumption is high in any one of the nodes, the chances of network’s life reduction due to path breaks are also more. On the other hand, node’s battery energy had to be consumed to guarantee high-level QoS in multicast routing to transmit correct data anywhere and at any time. Hence, the network lifetime should be considered as one objective of the multi-objective in the multicast routing problem.

Design/methodology/approach

Recently, many metaheuristic algorithms formulate the multicast routing problem as a single-objective problem, although it obviously is a multi-objective optimization problem. In the MOMR-DE, the network lifetime, cost, delay, jitter and bandwidth are considered as five objectives. Furthermore, three QoS constraints which are maximum allowed delay, maximum allowed jitter and minimum requested bandwidth are included. In addition, we modify the crossover and mutation operators to build the shortest-path multicast tree to maximize network lifetime and bandwidth, minimize cost, delay and jitter.

Findings

Two sets of experiments are conducted and compared with other algorithms for these problems. The simulation results show that our proposed method is capable of achieving faster convergence and is more preferable for multicast routing in MANET.

Originality/value

In MANET, most metaheuristic algorithms formulate the multicast routing problem as a single-objective problem. However, this paper proposes a multi-objective differential evolution algorithm to resolve multicast routing problem, and the proposed algorithm is capable of achieving faster convergence and more preferable for multicast routing.

Details

International Journal of Intelligent Computing and Cybernetics, vol. 11 no. 1
Type: Research Article
ISSN: 1756-378X

Keywords

1 – 10 of 260