A Passive Hopper With Lossless Collisions

A passive vertical hopping robot is here highly idealised as two vertically arranged masses acted on by gravity and coupled by a linear spring. The lower mass makes dead (e = 0) collisions with the rigid ground. The equations of motion can be reduced to a one dimensional map. Fixed points of the map are found in which case the robot hops incessantly. For these conservative solutions the lower mass collides with the ground with zero impact velocity. The interval of attraction for these conservative fixed points depends on system parameters.

Energy-Efficient Decentralized Routing with Localized Cooperation Suitable for Fast Fading

Wireless networks transmit information from a source to a destination via multiple hops in order to save energy and, thus, increase the lifetime of battery-operated nodes. The energy savings can be especially significant in cooperative transmission schemes, where several nodes cooperate during one hop to forward the information to the next node along a route to the destination. Finding the best multi-hop transmission policy in such a network which determines nodes that are involved in each hop, is a very important problem, but also a very difficult one especially when the physical wireless channel behavior is to be accounted for and exploited. We model the above optimization problem for randomly fading channels as a decentralized control problem – the channel observations available at each node define the information structure, while the control policy is defined by the power and phase of the signal transmitted by each node.In particular, we consider the problem of computing an energy-optimal cooperative transmission scheme in a wireless network for two different channel fading models: (i) slow fading channels, where the channel gains of the links remain the same for a large number of transmissions, and (ii) fast fading channels,where the channel gains of the links change quickly from one transmission to another. For slow fading, we consider a factored class of policies (corresponding to local cooperation between nodes), and show that the computation of an optimal policy in this class is equivalent to a shortest path computation on an induced graph, whose edge costs can be computed in a decentralized manner using only locally available channel state information(CSI). For fast fading, both CSI acquisition and data transmission consume energy. Hence, we need to jointly optimize over both these; we cast this optimization problem as a large stochastic optimization problem. We then jointly optimize over a set of CSI functions of the local channel states, and a corresponding factored class of control policies corresponding to local cooperation between nodes with a local outage constraint. The resulting optimal scheme in this class can again be computed efficiently in a decentralized manner. We demonstrate significant energy savings for both slow and fast fading channels through numerical simulations of randomly distributed networks.

Jointly Optimal Power Control and Hop Length for a Single Cell, Dense, Ad hoc Wireless Network

We consider a dense, ad hoc wireless network confined to a small region, such that direct communication is possible between any pair of nodes. The physical communication model is that a receiver decodes the signal from a single transmitter, while treating all other signals as interference. Data packets are sent between source-destination pairs by multihop relaying. We assume that nodes self-organise into a multihop network such that all hops are of length d meters, where d is a design parameter. There is a contention based multiaccess scheme, and it is assumed that every node always has data to send, either originated from it or a transit packet (saturation assumption). In this scenario, we seek to maximize a measure of the transport capacity of the network (measured in bit-meters per second) over power controls (in a fading environment) and over the hop distance d, subject to an average power constraint. We first argue that for a dense collection of nodes confined to a small region, single cell operation is efficient for single user decoding transceivers. Then, operating the dense ad hoc network (described above) as a single cell, we study the optimal hop length and power control that maximizes the transport capacity for a given network power constraint. More specifically, for a fading channel and for a fixed transmission time strategy (akin to the IEEE 802.11 TXOP), we find that there exists an intrinsic aggregate bit rate (Thetaopt bits per second, depending on the contention mechanism and the channel fading characteristics) carried by the network, when operating at the optimal hop length and power control. The optimal transport capacity is of the form dopt(Pmacrt) x Thetaopt with dopt scaling as Pmacrt 1 /eta, where Pmacrt is the available time average transmit power and eta is the path loss exponent. Under certain conditions on the fading distribution, we then pro- - vide a simple characterisation of the optimal operating point.

Optimal Hop Distance and Power Control for a Single Cell, Dense, Ad Hoc Wireless Network

We consider a dense, ad hoc wireless network, confined to a small region. The wireless network is operated as a single cell, i.e., only one successful transmission is supported at a time. Data packets are sent between source-destination pairs by multihop relaying. We assume that nodes self-organize into a multihop network such that all hops are of length d meters, where d is a design parameter. There is a contention-based multiaccess scheme, and it is assumed that every node always has data to send, either originated from it or a transit packet (saturation assumption). In this scenario, we seek to maximize a measure of the transport capacity of the network (measured in bit-meters per second) over power controls (in a fading environment) and over the hop distance d, subject to an average power constraint. We first motivate that for a dense collection of nodes confined to a small region, single cell operation is efficient for single user decoding transceivers. Then, operating the dense ad hoc wireless network (described above) as a single cell, we study the hop length and power control that maximizes the transport capacity for a given network power constraint. More specifically, for a fading channel and for a fixed transmission time strategy (akin to the IEEE 802.11 TXOP), we find that there exists an intrinsic aggregate bit rate (Theta(opt) bits per second, depending on the contention mechanism and the channel fading characteristics) carried by the network, when operating at the optimal hop length and power control. The optimal transport capacity is of the form d(opt)((P) over bar (t)) x Theta(opt) with d(opt) scaling as (P) over bar (t) (1/eta), where (P) over bar (t) is the available time average transmit power and eta is the path loss exponent. Under certain conditions on the fading distribution, we then provide a simple characterization of the optimal operating point. Simulation results are provided comparing the performance of the optimal strategy derived here with some simple strategies for operating the network.

Theory and Algorithms for Hop-Count-Based Localization with Random Geometric Graph Models of Dense Sensor Networks

Wireless sensor networks can often be viewed in terms of a uniform deployment of a large number of nodes in a region of Euclidean space. Following deployment, the nodes self-organize into a mesh topology with a key aspect being self-localization. Having obtained a mesh topology in a dense, homogeneous deployment, a frequently used approximation is to take the hop distance between nodes to be proportional to the Euclidean distance between them. In this work, we analyze this approximation through two complementary analyses. We assume that the mesh topology is a random geometric graph on the nodes; and that some nodes are designated as anchors with known locations. First, we obtain high probability bounds on the Euclidean distances of all nodes that are h hops away from a fixed anchor node. In the second analysis, we provide a heuristic argument that leads to a direct approximation for the density function of the Euclidean distance between two nodes that are separated by a hop distance h. This approximation is shown, through simulation, to very closely match the true density function. Localization algorithms that draw upon the preceding analyses are then proposed and shown to perform better than some of the well-known algorithms present in the literature. Belief-propagation-based message-passing is then used to further enhance the performance of the proposed localization algorithms. To our knowledge, this is the first usage of message-passing for hop-count-based self-localization.

Directional grain growth from anisotropic kinetic roughening of grain boundaries in sheared colloidal crystals

The fabrication of functional materials via grain growth engineering implicitly relies on altering the mobilities of grain boundaries (GBs) by applying external fields. Although computer simulations have alluded to kinetic roughening as a potential mechanism for modifying GB mobilities, its implications for grain growth have remained largely unexplored owing to difficulties in bridging the widely separated length and time scales. Here, by imaging GB particle dynamics as well as grain network evolution under shear, we present direct evidence for kinetic roughening of GBs and unravel its connection to grain growth in driven colloidal polycrystals. The capillary fluctuation method allows us to quantitatively extract shear-dependent effective mobilities. Remarkably, our experiments reveal that for sufficiently large strains, GBs with normals parallel to shear undergo preferential kinetic roughening, resulting in anisotropic enhancement of effective mobilities and hence directional grain growth. Single-particle level analysis shows that the mobility anisotropy emerges from strain-induced directional enhancement of activated particle hops normal to the GB plane. We expect our results to influence materials fabrication strategies for atomic and block copolymeric polycrystals as well.

Improving query focused summarization using look-ahead strategy

Query focused summarization is the task of producing a compressed text of original set of documents based on a query. Documents can be viewed as graph with sentences as nodes and edges can be added based on sentence similarity. Graph based ranking algorithms which use 'Biased random surfer model' like topic-sensitive LexRank have been successfully applied to query focused summarization. In these algorithms, random walk will be biased towards the sentences which contain query relevant words. Specifically, it is assumed that random surfer knows the query relevance score of the sentence to where he jumps. However, neighbourhood information of the sentence to where he jumps is completely ignored. In this paper, we propose look-ahead version of topic-sensitive LexRank. We assume that random surfer not only knows the query relevance of the sentence to where he jumps but he can also look N-step ahead from that sentence to find query relevance scores of future set of sentences. Using this look ahead information, we figure out the sentences which are indirectly related to the query by looking at number of hops to reach a sentence which has query relevant words. Then we make the random walk biased towards even to the indirect query relevant sentences along with the sentences which have query relevant words. Experimental results show 20.2% increase in ROUGE-2 score compared to topic-sensitive LexRank on DUC 2007 data set. Further, our system outperforms best systems in DUC 2006 and results are comparable to state of the art systems.

Modelling and analysis of new coolstreaming for P2P IPTV

Peer to peer networks are being used extensively nowadays for file sharing, video on demand and live streaming. For IPTV, delay deadlines are more stringent compared to file sharing. Coolstreaming was the first P2P IPTV system. In this paper, we model New Coolstreaming (newer version of Coolstreaming) via a queueing network. We use two time scale decomposition of Markov chains to compute the stationary distribution of number of peers and the expected number of substreams in the overlay which are not being received at the required rate due to parent overloading. We also characterize the end-to-end delay encountered by a video packet received by a user and originated at the server. Three factors contribute towards the delay. The first factor is the mean shortest path length between any two overlay peers in terms of overlay hops of the partnership graph which is shown to be O (log n) where n is the number of peers in the overlay. The second factor is the mean number of routers between any two overlay neighbours which is seen to be at most O (log N-I) where N-I is the number of routers in the internet. Third factor is the mean delay at a router in the internet. We provide an approximation of this mean delay E W]. Thus, the mean end to end delay in New Coolstreaming is shown to be upper bounded by O (log E N]) (log N-I) E (W)] where E N] is the mean number of peers at a channel.

Two-point correlation function of an exclusion process with hole-dependent rates

We consider an exclusion process on a ring in which a particle hops to an empty neighboring site with a rate that depends on the number of vacancies n in front of it. In the steady state, using the well-known mapping of this model to the zero-range process, we write down an exact formula for the partition function and the particle-particle correlation function in the canonical ensemble. In the thermodynamic limit, we find a simple analytical expression for the generating function of the correlation function. This result is applied to the hop rate u(n) = 1 + (b/n) for which a phase transition between high-density laminar phase and low-density jammed phase occurs for b > 2. For these rates, we find that at the critical density, the correlation function decays algebraically with a continuously varying exponent b - 2. We also calculate the two-point correlation function above the critical density and find that the correlation length diverges with a critical exponent nu = 1/(b - 2) for b < 3 and 1 for b > 3. These results are compared with those obtained using an exact series expansion for finite systems.

NrichD database: sequence databases enriched with computationally designed protein-like sequences aid in remote homology detection

NrichD ( ext-link-type=''uri'' xlink:href=''http://proline.biochem.iisc.ernet.in/NRICHD/'' xlink:type=''simple''>http://proline.biochem.iisc.ernet.in/NRICHD/)< /named-content> is a database of computationally designed protein-like sequences, augmented into natural sequence databases that can perform hops in protein sequence space to assist in the detection of remote relationships. Establishing protein relationships in the absence of structural evidence or natural `intermediately related sequences' is a challenging task. Recently, we have demonstrated that the computational design of artificial intermediary sequences/linkers is an effective approach to fill naturally occurring voids in protein sequence space. Through a large-scale assessment we have demonstrated that such sequences can be plugged into commonly employed search databases to improve the performance of routinely used sequence search methods in detecting remote relationships. Since it is anticipated that such data sets will be employed to establish protein relationships, two databases that have already captured these relationships at the structural and functional domain level, namely, the SCOP database and the Pfam database, have been `enriched' with these artificial intermediary sequences. NrichD database currently contains 3 611 010 artificial sequences that have been generated between 27 882 pairs of families from 374 SCOP folds. The data sets are freely available for download. Additional features include the design of artificial sequences between any two protein families of interest to the user.

QoS Constrained Optimal Sink and Relay Placement in Planned Wireless Sensor Networks

We are given a set of sensors at given locations, a set of potential locations for placing base stations (BSs, or sinks), and another set of potential locations for placing wireless relay nodes. There is a cost for placing a BS and a cost for placing a relay. The problem we consider is to select a set of BS locations, a set of relay locations, and an association of sensor nodes with the selected BS locations, so that the number of hops in the path from each sensor to its BS is bounded by h(max), and among all such feasible networks, the cost of the selected network is the minimum. The hop count bound suffices to ensure a certain probability of the data being delivered to the BS within a given maximum delay under a light traffic model. We observe that the problem is NP-Hard, and is hard to even approximate within a constant factor. For this problem, we propose a polynomial time approximation algorithm (SmartSelect) based on a relay placement algorithm proposed in our earlier work, along with a modification of the greedy algorithm for weighted set cover. We have analyzed the worst case approximation guarantee for this algorithm. We have also proposed a polynomial time heuristic to improve upon the solution provided by SmartSelect. Our numerical results demonstrate that the algorithms provide good quality solutions using very little computation time in various randomly generated network scenarios.

Molecular Antennas and Photoactive Nanomaterials based on Energy Transfer Processes

110 p.

Localização colaborativa em robótica de enxame.

Diversas das possíveis aplicações da robótica de enxame demandam que cada robô seja capaz de estimar a sua posição. A informação de localização dos robôs é necessária, por exemplo, para que cada elemento do enxame possa se posicionar dentro de uma formatura de robôs pré-definida. Da mesma forma, quando os robôs atuam como sensores móveis, a informação de posição é necessária para que seja possível identificar o local dos eventos medidos. Em virtude do tamanho, custo e energia dos dispositivos, bem como limitações impostas pelo ambiente de operação, a solução mais evidente, i.e. utilizar um Sistema de Posicionamento Global (GPS), torna-se muitas vezes inviável. O método proposto neste trabalho permite que as posições absolutas de um conjunto de nós desconhecidos sejam estimadas, com base nas coordenadas de um conjunto de nós de referência e nas medidas de distância tomadas entre os nós da rede. A solução é obtida por meio de uma estratégia de processamento distribuído, onde cada nó desconhecido estima sua própria posição e ajuda os seus vizinhos a calcular as suas respectivas coordenadas. A solução conta com um novo método denominado Multi-hop Collaborative Min-Max Localization (MCMM), ora proposto com o objetivo de melhorar a qualidade da posição inicial dos nós desconhecidos em caso de falhas durante o reconhecimento dos nós de referência. O refinamento das posições é feito com base nos algoritmos de busca por retrocesso (BSA) e de otimização por enxame de partículas (PSO), cujos desempenhos são comparados. Para compor a função objetivo, é introduzido um novo método para o cálculo do fator de confiança dos nós da rede, o Fator de Confiança pela Área Min-Max (MMA-CF), o qual é comparado com o Fator de Confiança por Saltos às Referências (HTA-CF), previamente existente. Com base no método de localização proposto, foram desenvolvidos quatro algoritmos, os quais são avaliados por meio de simulações realizadas no MATLABr e experimentos conduzidos em enxames de robôs do tipo Kilobot. O desempenho dos algoritmos é avaliado em problemas com diferentes topologias, quantidades de nós e proporção de nós de referência. O desempenho dos algoritmos é também comparado com o de outros algoritmos de localização, tendo apresentado resultados 40% a 51% melhores. Os resultados das simulações e dos experimentos demonstram a eficácia do método proposto.

Dynamic Server Selection in the Internet

As distributed information services like the World Wide Web become increasingly popular on the Internet, problems of scale are clearly evident. A promising technique that addresses many of these problems is service (or document) replication. However, when a service is replicated, clients then need the additional ability to find a "good" provider of that service. In this paper we report on techniques for finding good service providers without a priori knowledge of server location or network topology. We consider the use of two principal metrics for measuring distance in the Internet: hops, and round-trip latency. We show that these two metrics yield very different results in practice. Surprisingly, we show data indicating that the number of hops between two hosts in the Internet is not strongly correlated to round-trip latency. Thus, the distance in hops between two hosts is not necessarily a good predictor of the expected latency of a document transfer. Instead of using known or measured distances in hops, we show that the extra cost at runtime incurred by dynamic latency measurement is well justified based on the resulting improved performance. In addition we show that selection based on dynamic latency measurement performs much better in practice that any static selection scheme. Finally, the difference between the distribution of hops and latencies is fundamental enough to suggest differences in algorithms for server replication. We show that conclusions drawn about service replication based on the distribution of hops need to be revised when the distribution of latencies is considered instead.

DNS-based Internet Client Clustering and Characterization

This paper proposes a novel protocol which uses the Internet Domain Name System (DNS) to partition Web clients into disjoint sets, each of which is associated with a single DNS server. We define an L-DNS cluster to be a grouping of Web Clients that use the same Local DNS server to resolve Internet host names. We identify such clusters in real-time using data obtained from a Web Server in conjunction with that server's Authoritative DNS―both instrumented with an implementation of our clustering algorithm. Using these clusters, we perform measurements from four distinct Internet locations. Our results show that L-DNS clustering enables a better estimation of proximity of a Web Client to a Web Server than previously proposed techniques. Thus, in a Content Distribution Network, a DNS-based scheme that redirects a request from a web client to one of many servers based on the client's name server coordinates (e.g., hops/latency/loss-rates between the client and servers) would perform better with our algorithm.