H-NAMe: specifying, implementing and testing a hidden-node avoidance mechanism for wireless sensor networks

The hidden-node problem has been shown to be a major source of Quality-of-Service (QoS) degradation in Wireless Sensor Networks (WSNs) due to factors such as the limited communication range of sensor nodes, link asymmetry and the characteristics of the physical environment. In wireless contention-based Medium Access Control protocols, if two nodes that are not visible to each other transmit to a third node that is visible to the formers, there will be a collision – usually called hidden-node or blind collision. This problem greatly affects network throughput, energy-efficiency and message transfer delays, which might be particularly dramatic in large-scale WSNs. This technical report tackles the hidden-node problem in WSNs and proposes HNAMe, a simple yet efficient distributed mechanism to overcome it. H-NAMe relies on a grouping strategy that splits each cluster of a WSN into disjoint groups of non-hidden nodes and then scales to multiple clusters via a cluster grouping strategy that guarantees no transmission interference between overlapping clusters. We also show that the H-NAMe mechanism can be easily applied to the IEEE 802.15.4/ZigBee protocols with only minor add-ons and ensuring backward compatibility with the standard specifications. We demonstrate the feasibility of H-NAMe via an experimental test-bed, showing that it increases network throughput and transmission success probability up to twice the values obtained without H-NAMe. We believe that the results in this technical report will be quite useful in efficiently enabling IEEE 802.15.4/ZigBee as a WSN protocol.

Static-priority scheduling over wireless networks with multiple broadcast domains

We propose a wireless medium access control (MAC) protocol that provides static-priority scheduling of messages in a guaranteed collision-free manner. Our protocol supports multiple broadcast domains, resolves the wireless hidden terminal problem and allows for parallel transmissions across a mesh network. Arbitration of messages is achieved without the notion of a master coordinating node, global clock synchronization or out-of-band signaling. The protocol relies on bit-dominance similar to what is used in the CAN bus except that in order to operate on a wireless physical layer, nodes are not required to receive incoming bits while transmitting. The use of bit-dominance efficiently allows for a much larger number of priorities than would be possible using existing wireless solutions. A MAC protocol with these properties enables schedulability analysis of sporadic message streams in wireless multihop networks.

Delay-bounded medium access for unidirectional wireless links

Consider a wireless network where links may be unidirectional, that is, a computer node A can broadcast a message and computer node B will receive this message but if B broadcasts then A will not receive it. Assume that messages have deadlines. We propose a medium access control (MAC) protocol which replicates a message in time with carefully selected pauses between replicas, and in this way it guarantees that for every message at least one replica of that message is transmitted without collision. The protocol ensures this with no knowledge of the network topology and it requires neither synchronized clocks nor carrier sensing capabilities. We believe this result is significant because it is the only MAC protocol that offers an upper bound on the message queuing delay for unidirectional links without relying on synchronized clocks.

H-NAMe: a hidden-node avoidance mechanism for wireless sensor networks

The hidden-node problem has been shown to be a major source of Quality-of-Service (QoS) degradation in Wireless Sensor Networks (WSNs) due to factors such as the limited communication range of sensor nodes, link asymmetry and the characteristics of the physical environment. In wireless contention-based Medium Access Control protocols, if two nodes that are not visible to each other transmit to a third node that is visible to the formers, there will be a collision – usually called hidden-node or blind collision. This problem greatly affects network throughput, energy-efficiency and message transfer delays, which might be particularly dramatic in large-scale WSNs. This paper tackles the hiddennode problem in WSNs and proposes H-NAMe, a simple yet efficient distributed mechanism to overcome it. H-NAMe relies on a grouping strategy that splits each cluster of a WSN into disjoint groups of non-hidden nodes and then scales to multiple clusters via a cluster grouping strategy that guarantees no transmission interference between overlapping clusters. We also show that the H-NAMe mechanism can be easily applied to the IEEE 802.15.4/ZigBee protocols with only minor add-ons and ensuring backward compatibility with the standard specifications. We demonstrate the feasibility of H-NAMe via an experimental test-bed, showing that it increases network throughput and transmission success probability up to twice the values obtained without H-NAMe. We believe that the results in this paper will be quite useful in efficiently enabling IEEE 802.15.4/ZigBee as a WSN protocol

Competitive dynamics for behavior coordination in a joint transportation task

We address the problem of coordinating two non-holonomic mobile robots that move in formation while transporting a long payload. A competitive dynamics is introduced that gradually controls the activation and deactivation of individual behaviors. This process introduces (asymmetrical) hysteresis during behavioral switching. As a result behavioral oscillations, due to noisy information, are eliminated. Results in indoor environments show that if parameter values are chosen within reasonable ranges then, in spite of noise in the robots communi- cation and sensors, the overall robotic system works quite well even in cluttered environments. The robots overt behavior is stable and smooth.

Implementation of a dominance protocol for wireless medium access

Consider the problem of scheduling sporadic message transmission requests with deadlines. For wired channels, this has been achieved successfully using the CAN bus. For wireless channels, researchers have recently proposed a similar solution; a collision-free medium access control (MAC) protocol that implements static-priority scheduling. Unfortunately no implementation has been reported, yet. We implement and evaluate it to find that the implementation indeed is collision-free and prioritized. This allows us to develop schedulability analysis for the implementation. We measure the response times of messages in our implementation and find that our new response-time analysis indeed offers an upper bound on the response times. This enables a new class of wireless real-time systems with timeliness guarantees for sporadic messages and it opens-up a new research area: schedulability analysis for wireless networks.

Critical reappraisal of Late Mesozoic-Cenozoic Central and North Atlantic, Caribbean and Mediterranean evolution

(l) The Pacific basin (Pacific area) may be regarded as moving eastwards like a double zip fastener relative to the continents and their respective plates (Pangaea area): opening in the East and closing in the West. This movement is tracked by a continuous mountain belt, the collision ages of which increase westwards. (2) The relative movements between the Pacific area and the Pangaea area in the W-EfE-W direction are generated by tidal forces (principle of hypocycloid gearing), whereby the lower mantle and the Pacific basin or area (Pacific crust = roof of the lower mantle?) rotate somewhat faster eastwards around the Earth's spin axis relative to the upper mantle/crust system with the continents and their respective plates (Pangaea area) (differential rotation). (3) These relative West to East/East to West displacements produce a perpetually existing sequence of distinct styles of opening and closing oeean basins, exemplified by the present East to West arrangement of ocean basins around the globe (Oceanic or Wilson Cycle: Rift/Red Sea style; Atlantic style; Mediterranean/Caribbean style as eastwards propagating tongue of the Pacific basin; Pacific style; Collision/Himalayas style). This sequence of ocean styles, of which the Pacific ocean is a part, moves eastwards with the lower mantle relative to the continents and the upper-mantle/crust of the Pangaea area. (4) Similarly, the collisional mountain belt extending westwards from the equator to the West of the Pacific and representing a chronological sequence of collision zones (sequential collisions) in the wake of the passing of the Pacific basin double zip fastener, may also be described as recording the history of oceans and their continental margins in the form of successive Wilson Cycles. (5) Every 200 to 250 m.y. the Pacific basin double zip fastener, the sequence of ocean styles of the Wilson Cycle and the eastwards growing collisional mountain belt in their wake complete one lap around the Earth. Two East drift lappings of 400 to 500 m.y. produce a two-lap collisional mountain belt spiral around a supercontinent in one hemisphere (North or South Pangaea). The Earth's history is subdivided into alternating North Pangaea growth/South Pangaea breakup eras and South Pangaea growth/North Pangaea breakup eras. Older North and South Pangaeas and their collisional mountain belt spirals may be reconstructed by rotating back the continents and orogenic fragments of a broken spiral (e.g. South Pangaea, Gondwana) to their previous Pangaea growth era orientations. In the resulting collisional mountain belt spiral, pieced together from orogenic segments and fragments, the collision ages have to increase successively towards the West. (6) With its current western margin orientated in a West-East direction North America must have collided during the Late Cretaceous Laramide orogeny with the northern margin of South America (Caribbean Andes) at the equator to the West of the Late Mesozoic Pacific. During post-Laramide times it must have rotated clockwise into its present orientation. The eastern margin of North America has never been attached to the western margin of North Africa but only to the western margin of Europe. (7) Due to migration eastwards of the sequence of ocean styles of the Wilson Cycle, relative to a distinct plate tectonic setting of an ocean, a continent or continental margin, a future or later evolutionary style at the Earth's surface is always depicted in a setting simultaneously developed further to the West and a past or earlier style in a setting simultaneously occurring further to the East. In consequence, ahigh probability exists that up to the Early Tertiary, Greenland (the ArabiaofSouth America?) occupied a plate tectonic setting which is comparable to the current setting of Arabia (the Greenland of Africa?). The Late Cretaceous/Early Tertiary Eureka collision zone (Eureka orogeny) at the northern margin of the Greenland Plate and on some of the Canadian Arctic Islands is comparable with the Middle to Late Tertiary Taurus-Bitlis-Zagros collision zone at the northern margin of the Arabian Plate.

Multi-criteria optimization manipulator trajectory planning

In the last twenty years genetic algorithms (GAs) were applied in a plethora of fields such as: control, system identification, robotics, planning and scheduling, image processing, and pattern and speech recognition (Bäck et al., 1997). In robotics the problems of trajectory planning, collision avoidance and manipulator structure design considering a single criteria has been solved using several techniques (Alander, 2003). Most engineering applications require the optimization of several criteria simultaneously. Often the problems are complex, include discrete and continuous variables and there is no prior knowledge about the search space. These kind of problems are very more complex, since they consider multiple design criteria simultaneously within the optimization procedure. This is known as a multi-criteria (or multiobjective) optimization, that has been addressed successfully through GAs (Deb, 2001). The overall aim of multi-criteria evolutionary algorithms is to achieve a set of non-dominated optimal solutions known as Pareto front. At the end of the optimization procedure, instead of a single optimal (or near optimal) solution, the decision maker can select a solution from the Pareto front. Some of the key issues in multi-criteria GAs are: i) the number of objectives, ii) to obtain a Pareto front as wide as possible and iii) to achieve a Pareto front uniformly spread. Indeed, multi-objective techniques using GAs have been increasing in relevance as a research area. In 1989, Goldberg suggested the use of a GA to solve multi-objective problems and since then other researchers have been developing new methods, such as the multi-objective genetic algorithm (MOGA) (Fonseca & Fleming, 1995), the non-dominated sorted genetic algorithm (NSGA) (Deb, 2001), and the niched Pareto genetic algorithm (NPGA) (Horn et al., 1994), among several other variants (Coello, 1998). In this work the trajectory planning problem considers: i) robots with 2 and 3 degrees of freedom (dof ), ii) the inclusion of obstacles in the workspace and iii) up to five criteria that are used to qualify the evolving trajectory, namely the: joint traveling distance, joint velocity, end effector / Cartesian distance, end effector / Cartesian velocity and energy involved. These criteria are used to minimize the joint and end effector traveled distance, trajectory ripple and energy required by the manipulator to reach at destination point. Bearing this ideas in mind, the paper addresses the planning of robot trajectories, meaning the development of an algorithm to find a continuous motion that takes the manipulator from a given starting configuration up to a desired end position without colliding with any obstacle in the workspace. The chapter is organized as follows. Section 2 describes the trajectory planning and several approaches proposed in the literature. Section 3 formulates the problem, namely the representation adopted to solve the trajectory planning and the objectives considered in the optimization. Section 4 studies the algorithm convergence. Section 5 studies a 2R manipulator (i.e., a robot with two rotational joints/links) when the optimization trajectory considers two and five objectives. Sections 6 and 7 show the results for the 3R redundant manipulator with five goals and for other complementary experiments are described, respectively. Finally, section 8 draws the main conclusions.

Neutral C60 effusive source for atomic collisions with fullerene

Review of scientific instruments, Vol.72, Nº9

Critical reappraisal of Late Mesozoic-Cenozoic Central and North Atlantic, Caribbean and Mediterranean evolution

(l) The Pacific basin (Pacific area) may be regarded as moving eastwards like a double zip fastener relative to the continents and their respective plates (Pangaea area): opening in the East and closing in the West. This movement is tracked by a continuous mountain belt, the collision ages of which increase westwards. (2) The relative movements between the Pacific area and the Pangaea area in the W-E/E-W direction are generated by tidal forces (principle of hypocycloid gearing), whereby the lower mantle and the Pacific basin or area (Pacific crust = roof of the lower mantle?) rotate somewhat faster eastwards around the Earth's spin axis relative to the upper mantle/crust system with the continents and their respective plates (Pangaea area) (differential rotation). (3) These relative West to East/East to West displacements produce a perpetually existing sequence of distinct styles of opening and closing ocean basins, exemplified by the present East to West arrangement of ocean basins around the globe (Oceanic or Wilson Cycle: Rift/Red Sea style; Atlantic style; Mediterranean/Caribbean style as eastwards propagating tongue of the Pacific basin; Pacific style; Collision/Himalayas style). This sequence of ocean styles, of which the Pacific ocean is a part, moves eastwards with the lower mantle relative to the continents and the upper-mantle/crust of the Pangaea area. (4) Similarly, the collisional mountain belt extending westwards from the equator to the West of the Pacific and representing a chronological sequence of collision zones (sequential collisions) in the wake of the passing of the Pacific basin double zip fastener, may also be described as recording the history of oceans and their continental margins in the form of successive Wilson Cycles. (5) Every 200 to 250 m.y. the Pacific basin double zip fastener, the sequence of ocean styles of the Wilson Cycle and the eastwards growing collisional mountain belt in their wake complete one lap around the Earth. Two East drift lappings of 400 to 500 m.y. produce a two-lap collisional mountain belt spiral around a supercontinent in one hemisphere (North or South Pangaea). The Earth's history is subdivided into alternating North Pangaea growth/South Pangaea breakup eras and South Pangaea growth/North Pangaea breakup eras. Older North and South Pangaeas and their collisional mountain belt spirals may be reconstructed by rotating back the continents and orogenic fragments of a broken spiral (e.g. South Pangaea, Gondwana) to their previous Pangaea growth era orientations. In the resulting collisional mountain belt spiral, pieced together from orogenic segments and fragments, the collision ages have to increase successively towards the West. (6) With its current western margin orientated in a West-East direction North America must have collided during the Late Cretaceous Laramide orogeny with the northern margin of South America (Caribbean Andes) at the equator to the West of the Late Mesozoic Pacific. During post-Laramide times it must have rotated clockwise into its present orientation. The eastern margin of North America has never been attached to the western margin of North Africa but only to the western margin of Europe. (7) Due to migration eastwards of the sequence of ocean styles of the Wilson Cycle, relative to a distinct plate tectonic setting of an ocean, a continent or continental margin, a future or later evolutionary style at the Earth's surface is always depicted in a setting simultaneously developed further to the West and a past or earlier style in a setting simultaneously occurring further to the East. In consequence, ahigh probability exists that up to the Early Tertiary, Greenland (the ArabiaofSouth America?) occupied a plate tectonic setting which is comparable to the current setting of Arabia (the Greenland of Africa?). The Late Cretaceous/Early Tertiary Eureka collision zone (Eureka orogeny) at the northern margin of the Greenland Plate and on some of the Canadian Arctic Islands is comparable with the Middle to Late Tertiary Taurus-Bitlis-Zagros collision zone at the northern margin of the Arabian Plate.

Estimation of the Crustal Bulk Properties Beneath Mainland Portugal from P-Wave Teleseismic Receiver Functions

In this work, we present results from teleseismic P-wave receiver functions (PRFs) obtained in Portugal, Western Iberia. A dense seismic station deployment conducted between 2010 and 2012, in the scope of the WILAS project and covering the entire country, allowed the most spatially extensive probing on the bulk crustal seismic properties of Portugal up to date. The application of the H-κ stacking algorithm to the PRFs enabled us to estimate the crustal thickness (H) and the average crustal ratio of the P- and S-waves velocities V p/V s (κ) for the region. Observations of Moho conversions indicate that this interface is relatively smooth with the crustal thickness ranging between 24 and 34 km, with an average of 30 km. The highest V p/V s values are found on the Mesozoic-Cenozoic crust beneath the western and southern coastal domain of Portugal, whereas the lowest values correspond to Palaeozoic crust underlying the remaining part of the subject area. An average V p/V s is found to be 1.72, ranging 1.63-1.86 across the study area, indicating a predominantly felsic composition. Overall, we systematically observe a decrease of V p/V s with increasing crustal thickness. Taken as a whole, our results indicate a clear distinction between the geological zones of the Variscan Iberian Massif in Portugal, the overall shape of the anomalies conditioned by the shape of the Ibero-Armorican Arc, and associated Late Paleozoic suture zones, and the Meso-Cenozoic basin associated with Atlantic rifting stages. Thickened crust (30-34 km) across the studied region may be inherited from continental collision during the Paleozoic Variscan orogeny. An anomalous crustal thinning to around 28 km is observed beneath the central part of the Central Iberian Zone and the eastern part of South Portuguese Zone.

Acceleration of physics simulation engine through OpenCL

Dissertação para obtenção do Grau de Mestre em Engenharia Informática

A Random Access Protocol incorporating Multi-Packet Reception, Retransmission Diversity and Successive Interference Cancellation

8th International Workshop on Multiple Access Communications (MACOM2015), Helsinki, Finland.

Multi-Objective and Financial Portfolio Optimization of Carrier-Sense Multiple Access Protocols with Cooperative Diversity

8th International Workshop on Multiple Access Communications (MACOM2015), Helsinki, Finland.

Scalable and interference aware wi-fi mesh networks using cots devices

A crescente tendencia no acesso móvel tem sido potenciada pela tecnologia IEEE 802.11. Contudo, estas redes têm alcance rádio limitado. Para a extensão da sua cobertura é possível recorrer a redes emalhadas sem fios baseadas na tecnologia IEEE 802.11, com vantagem do ponto de vista do custo e da flexibilidade de instalação, face a soluções cabladas. Redes emalhadas sem fios constituídas por nós com apenas uma interface têm escalabilidade reduzida. A principal razão dessa limitação deve-se ao uso do mecanismo de acesso ao meio partilhado Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA) em topologias multi-hop. Especificamente, o CSMA/CA não evita o problema do nó escondido levando ao aumento do número de colisões e correspondente degradação de desempenho com impacto direto no throughput e na latência. Com a redução da tecnologia rádio torna-se viável a utilização de múltiplos rádios por nó, sem com isso aumentar significativamente o custo da solução final de comunicações. A utilização de mais do que um rádio por nó de comuniações permite superar os problemas de desempenho inerentes ás redes formadas por nós com apenas um rádio. O objetivo desta tese, passa por desenvolver uma nova solução para redes emalhadas multi-cana, duar-radio, utilizando para isso novos mecanismos que complementam os mecanismos definidos no IEEE 802.11 para o estabelecimento de um Basic Service Set (BSS). A solução é baseada na solução WiFIX, um protocolo de routing para redes emalhadas de interface única e reutiliza os mecanismos já implementados nas redes IEEE 802.11 para difundir métricas que permitam à rede escalar de forma eficaz minimizando o impacto na performance. A rede multi-hop é formada por nós equipados com duas interfaces, organizados numa topologia hierárquica sobre múltiplas relações Access Point (AP) – Station (STA). Os resultados experimentais obtidos mostram a eficácia e o bom desempenho da solução proposta face à solução WiFIX original.