Co-operating retrodirective system

Practical demonstration of the operational advantages gained through the use of a co-operating retrodirective array (RDA) basestation and Van Atta node arrangements is discussed. The system exploits a number of inherent RDA features to provide analogue real time multifunctional operation at low physical complexity. An active dual-conversion four element RDA is used as the power distribution source (basestation) while simultaneously achieving a receive sensitivity level of ??109 dBm and 3 dB automatic beam steering angle of ??45??. When mobile units are each equipped with a semi-passive four element Van Atta array, it is shown mobile device orientation issues are mitigated and optimal energy transfer can occur because of automatic beam formation resulting from retrodirective self-pointing action. We show that operation in multipath rich environments with or without line of sight acts to reduce average power density limits in the operating volume with high energy density occurring at mobile nodes sites only. The system described can be used as a full duplex ASK communications link, or, as a means for remote node charging by wireless means, thereby enhancing deployment opportunities between unstabilised moving platforms.

Voltage Sensing Using an Asynchronous Charge-to-Digital Converter for Energy-Autonomous Environments

In future systems with relatively unreliable and unpredictable energy sources such as harvesters, the system power supply may become non-deterministic. For energy effective operations, Vdd is an important parameter in any meaningful system control mechanism. Reliable and accurate on-chip voltage sensors are therefore indispensible for the power and computation management of such systems. Existing voltage sensing methods are not suitable because they usually require a stable and known reference (voltage, current, time, frequency, etc.), which is difficult to obtain in this environment. This paper describes an autonomous reference-free voltage sensor designed using an asynchronous counter powered by the charge on a capacitor and a small controller. Unlike existing methods, the voltage information is directly generated as a digital code. The sensor, fabricated in the 180 nm technology node, was tested successfully through performing measurements over the voltage range from 1.8 V down to 0.8 V.

The Forgiving Graph: a distributed data structure for low stretch under adversarial attack

We consider the problem of self-healing in peer-to-peer networks that are under repeated attack by an omniscient adversary. We assume that, over a sequence of rounds, an adversary either inserts a node with arbitrary connections or deletes an arbitrary node from the network. The network responds to each such change by quick “repairs,” which consist of adding or deleting a small number of edges. These repairs essentially preserve closeness of nodes after adversarial deletions, without increasing node degrees by too much, in the following sense. At any point in the algorithm, nodes v and w whose distance would have been l in the graph formed by considering only the adversarial insertions (not the adversarial deletions), will be at distance at most l log n in the actual graph, where n is the total number of vertices seen so far. Similarly, at any point, a node v whose degree would have been d in the graph with adversarial insertions only, will have degree at most 3d in the actual graph. Our distributed data structure, which we call the Forgiving Graph, has low latency and bandwidth requirements. The Forgiving Graph improves on the Forgiving Tree distributed data structure from Hayes et al. (2008) in the following ways: 1) it ensures low stretch over all pairs of nodes, while the Forgiving Tree only ensures low diameter increase; 2) it handles both node insertions and deletions, while the Forgiving Tree only handles deletions; 3) it requires only a very simple and minimal initialization phase, while the Forgiving Tree initially requires construction of a spanning tree of the network.

End-to-End QoS Enhancement ofHSDPA End-User Multi-flow Traffic Using RAN Buffer Management

High speed downlink packet access (HSDPA) was introduced to UMTS radio access segment to provide higher capacity for new packet switched services. As a result, packet switched sessions with multiple diverse traffic flows such as concurrent voice and data, or video and data being transmitted to the same user are a likely commonplace cellular packet data scenario. In HSDPA, radio access network (RAN) buffer management schemes are essential to support the end-to-end QoS of such sessions. Hence in this paper we present the end-to-end performance study of a proposed RAN buffer management scheme for multi-flow sessions via dynamic system-level HSDPA simulations. The scheme is an enhancement of a time-space priority (TSP) queuing strategy applied to the node B MAC-hs buffer allocated to an end user with concurrent real-time (RT) and non-real-time (NRT) flows during a multi-flow session. The experimental multi- flow scenario is a packet voice call with concurrent TCP-based file download to the same user. Results show that with the proposed enhancements to the TSP-based RAN buffer management, end-to-end QoS performance gains accrue to the NRT flow without compromising RT flow QoS of the same end user session

Buffer Management for Multimedia QoS control over HSDPA Downlink

HSDPA specifications include support for a flexible framework for QoS management. In this paper, it is shown how buffer management could be incorporated into HSDPA QoS framework for 'multimedia' traffic QoS control in the MAC-hs of the Node-B. A time-space-priority (TSP) scheme is proposed as viable buffer management scheme to this effect. Comparative simulation study with other schemes is presented, demonstrating the effectiveness of the TSP buffer management scheme for 'multimedia' service QoS control in HSDPA Node-B data buffers

On the Complexity of Universal Leader Election

Electing a leader is a fundamental task in distributed computing. In its implicit version, only the leader must know who is the elected leader. This paper focuses on studying the message and time complexity of randomized implicit leader election in synchronous distributed networks. Surprisingly, the most "obvious" complexity bounds have not been proven for randomized algorithms. The "obvious" lower bounds of O(m) messages (m is the number of edges in the network) and O(D) time (D is the network diameter) are non-trivial to show for randomized (Monte Carlo) algorithms. (Recent results that show that even O(n) (n is the number of nodes in the network) is not a lower bound on the messages in complete networks, make the above bounds somewhat less obvious). To the best of our knowledge, these basic lower bounds have not been established even for deterministic algorithms (except for the limited case of comparison algorithms, where it was also required that some nodes may not wake up spontaneously, and that D and n were not known).

We establish these fundamental lower bounds in this paper for the general case, even for randomized Monte Carlo algorithms. Our lower bounds are universal in the sense that they hold for all universal algorithms (such algorithms should work for all graphs), apply to every D, m, and n, and hold even if D, m, and n are known, all the nodes wake up simultaneously, and the algorithms can make anyuse of node's identities. To show that these bounds are tight, we present an O(m) messages algorithm. An O(D) time algorithm is known. A slight adaptation of our lower bound technique gives rise to an O(m) message lower bound for randomized broadcast algorithms.

An interesting fundamental problem is whether both upper bounds (messages and time) can be reached simultaneously in the randomized setting for all graphs. (The answer is known to be negative in the deterministic setting). We answer this problem partially by presenting a randomized algorithm that matches both complexities in some cases. This already separates (for some cases) randomized algorithms from deterministic ones. As first steps towards the general case, we present several universal leader election algorithms with bounds that trade-off messages versus time. We view our results as a step towards understanding the complexity of universal leader election in distributed networks.

Sublinear Bounds for Randomized Leader Election

This paper concerns randomized leader election in synchronous distributed networks. A distributed leader election algorithm is presented for complete n-node networks that runs in O(1) rounds and (with high probability) takes only O(n-vlog3/2n) messages to elect a unique leader (with high probability). This algorithm is then extended to solve leader election on any connected non-bipartiten-node graph G in O(t(G)) time and O(t(G)n-vlog3/2n) messages, where t(G) is the mixing time of a random walk on G. The above result implies highly efficient (sublinear running time and messages) leader election algorithms for networks with small mixing times, such as expanders and hypercubes. In contrast, previous leader election algorithms had at least linear message complexity even in complete graphs. Moreover, super-linear message lower bounds are known for time-efficientdeterministic leader election algorithms. Finally, an almost-tight lower bound is presented for randomized leader election, showing that O(n-v) messages are needed for any O(1) time leader election algorithm which succeeds with high probability. It is also shown that O(n 1/3) messages are needed by any leader election algorithm that succeeds with high probability, regardless of the number of the rounds. We view our results as a step towards understanding the randomized complexity of leader election in distributed networks.

Context-Aware Body Area Networks (CABAN) for interactive smart environments:Interference characterization

Body Area Networks are unique in that the large-scale mobility of users allows the network itself to travel across a diverse range of operating domains or even to enter new and unknown environments. This network mobility is unlike node mobility in that sensed changes in inter-network interference level may be used to identify opportunities for intelligent inter-networking, for example, by merging or splitting from other networks, thus providing an extra degree of freedom. This paper introduces the concept of context-aware bodynets for interactive environments using inter-network interference sensing. New ideas are explored at both the physical and link layers with an investigation based on a 'smart' office environment. A series of carefully controlled measurements of the mesh interconnectivity both within and between an ambulatory body area network and a stationary desk-based network were performed using 2.45 GHz nodes. Received signal strength and carrier to interference ratio time series for selected node to node links are presented. The results provide an insight into the potential interference between the mobile and static networks and highlight the possibility for automatic identification of network merging and splitting opportunities. © 2010 ACM.

Xheal: A localized self-healing algorithm using expanders

We consider the problem of self-healing in reconfigurable networks e.g., peer-to-peer and wireless mesh networks. For such networks under repeated attack by an omniscient adversary, we propose a fully distributed algorithm, Xheal, that maintains good expansion and spectral properties of the network, while keeping the network connected. Moreover, Xheal does this while allowing only low stretch and degree increase per node. The algorithm heals global properties like expansion and stretch while only doing local changes and using only local information. We also provide bounds on the second smallest eigenvalue of the Laplacian which captures key properties such as mixing time, conductance, congestion in routing etc. Xheal has low amortized latency and bandwidth requirements. Our work improves over the self-healing algorithms Forgiving tree [PODC 2008] andForgiving graph [PODC 2009] in that we are able to give guarantees on degree and stretch, while at the same time preserving the expansion and spectral properties of the network.

Dense subgraphs on dynamic networks

In distributed networks, it is often useful for the nodes to be aware of dense subgraphs, e.g., such a dense subgraph could reveal dense substructures in otherwise sparse graphs (e.g. the World Wide Web or social networks); these might reveal community clusters or dense regions for possibly maintaining good communication infrastructure. In this work, we address the problem of self-awareness of nodes in a dynamic network with regards to graph density, i.e., we give distributed algorithms for maintaining dense subgraphs that the member nodes are aware of. The only knowledge that the nodes need is that of the dynamic diameter D, i.e., the maximum number of rounds it takes for a message to traverse the dynamic network. For our work, we consider a model where the number of nodes are fixed, but a powerful adversary can add or remove a limited number of edges from the network at each time step. The communication is by broadcast only and follows the CONGEST model. Our algorithms are continuously executed on the network, and at any time (after some initialization) each node will be aware if it is part (or not) of a particular dense subgraph. We give algorithms that (2 + e)-approximate the densest subgraph and (3 + e)-approximate the at-least-k-densest subgraph (for a given parameter k). Our algorithms work for a wide range of parameter values and run in O(D log n) time. Further, a special case of our results also gives the first fully decentralized approximation algorithms for densest and at-least-k-densest subgraph problems for static distributed graphs. © 2012 Springer-Verlag.

The forgiving tree: a self-healing distributed data structure

We consider the problem of self-healing in peer-to-peer networks that are under repeated attack by an omniscient adversary. We assume that the following process continues for up to n rounds where n is the total number of nodes initially in the network: the adversary deletesan arbitrary node from the network, then the network responds by quickly adding a small number of new edges.

We present a distributed data structure that ensures two key properties. First, the diameter of the network is never more than O(log Delta) times its original diameter, where Delta is the maximum degree of the network initially. We note that for many peer-to-peer systems, Delta is polylogarithmic, so the diameter increase would be a O(loglog n) multiplicative factor. Second, the degree of any node never increases by more than 3 over its original degree. Our data structure is fully distributed, has O(1) latency per round and requires each node to send and receive O(1) messages per round. The data structure requires an initial setup phase that has latency equal to the diameter of the original network, and requires, with high probability, each node v to send O(log n) messages along every edge incident to v. Our approach is orthogonal and complementary to traditional topology-based approaches to defending against attack.

Picking up the Pieces: Self-Healing in reconfigurable networks

We consider the problem of self-healing in networks that are reconfigurable in the sense that they can change their topology during an attack. Our goal is to maintain connectivity in these networks, even in the presence of repeated adversarial node deletion, by carefully adding edges after each attack. We present a new algorithm, DASH, that provably ensures that: 1) the network stays connected even if an adversary deletes up to all nodes in the network; and 2) no node ever increases its degree by more than 2 log n, where n is the number of nodes initially in the network. DASH is fully distributed; adds new edges only among neighbors of deleted nodes; and has average latency and bandwidth costs that are at most logarithmic in n. DASH has these properties irrespective of the topology of the initial network, and is thus orthogonal and complementary to traditional topology- based approaches to defending against attack. We also prove lower-bounds showing that DASH is asymptotically optimal in terms of minimizing maximum degree increase over multiple attacks. Finally, we present empirical results on power-law graphs that show that DASH performs well in practice, and that it significantly outperforms naive algorithms in reducing maximum degree increase.