A weakly universal cellular automaton on the pentagrid with two states

In this paper, we prove that there is a weakly universal cellular automaton on the pentagrid with two states. This paper improves in some sense a previous result with three states. Both results make use of a la Moore neighbourhood. However, the result with three states is rotation invariant while the result of the present paper is not. In both cases, at each step of the computation, the set of non quiescent states has always infinitely many cycles.     

A network flow based approach for network selection in dynamic spectrum access networks

In this paper, we present a network flow based approach for dynamic network and channel selection for secondary users in dynamic spectrum access networks. Most approaches in the current literature on dynamic spectrum access networks do not consider dynamic network and channel selection. We present a network flow framework for network selection. We show that our approach can enable re-assignment of networks to secondary users and also re-assignment of channels to secondary users within the same network. The assignments and re-assignments take into account, the interference caused to primary users, the price each secondary user is willing to pay and the quality of service (QoS) obtained by each secondary user. We obtain a bound for the maximum number of re-assignments.     

Prowling autonomous mobile robot with a network camera

This research aimed to develop an autonomous mobile robot that helps various kinds of people. The evasion of obstacles is absolutely imperative so that the robot can act in a human-life environment. Therefore, we developed a robot that moves through doors and avoids obstacles with the help of images taken by a camera set on the robot. This work was presented in part at the 13th International Symposium on Artifical Life and Robotics, Oita, Japan, January 31–February 2, 2008     

A 4-states algebraic solution to linear cellular automata synchronization

In this paper, we aim to present a completely new solution to the firing squad synchronization problem based on Wolfram's rule 60. This solution solves the problem on an infinite number of lines but not all possible lines. The two remarkable properties are that the state complexity of it is the lowest possible, say 4 states and 32 transitions (we prove that no line of length n?5 can be synchronized with only 3 states) and that the algorithm is no more based on geometric constructions but relies on some algebraic properties of the transition function. The solution is almost in minimal time: up to one unit of time.     

A cellular automaton model of particle motions and its applications

A natural object such as a flame with smoke is featured in terms of ambiguous boundaries and complex motion. One way of modeling natural objects is by particle systems, which need a large amount of computation time to calculate interactions among the particles. This paper deseribes another way of modeling particle motions based on a cellular automaton. Cellular automata are massively parallel computation models that can simulate complex phenomena. In our model, particle motions are simulated in a cellular space with a Margolus neighborhood, which has good conservation properties and collision detectability. This paper shows several applications in two-dimensional cellular space.     

Parallel discovery of network motifs

Many natural structures can be naturally represented by complex networks. Discovering network motifs, which are overrepresented patterns of inter-connections, is a computationally hard task related to graph isomorphism. Sequential methods are hindered by an exponential execution time growth when we increase the size of motifs and networks. In this article we study the opportunities for parallelism in existing methods and propose new parallel strategies that adapt and extend one of the most efficient serial methods known from the Fanmod tool. We propose both a master–worker strategy and one with distributed control, in which we employ a randomized receiver initiated methodology capable of providing dynamic load balancing during the whole computation process. Our strategies are capable of dealing both with exact and approximate network motif discovery. We implement and apply our algorithms to a set of representative networks and examine their scalability up to 128 processing cores. We obtain almost linear speedups, showcasing the efficiency of our proposed approach and are able to reach motif sizes that were not previously achievable using conventional serial algorithms.     

A Coral Reefs Optimization algorithm for optimal mobile network deployment with electromagnetic pollution control criterion

In this paper we apply a novel meta-heuristic approach, the Coral Reefs Optimization (CRO) algorithm, to solve a Mobile Network Deployment Problem (MNDP), in which the control of the electromagnetic pollution plays an important role. The CRO is a new bio-inspired meta-heuristic algorithm based on the growing and evolution of coral reefs. The aim of this paper is therefore twofold: first of all, we study the performance of the CRO approach in a real hard optimization problem, and second, we solve an important problem in the field of telecommunications, including the minimization of electromagnetic pollution as a key concept in the problem. We show that the CRO is able to obtain excellent solutions to the MNDP in a real instance in Alcalá de Henares (Madrid, Spain), improving the results obtained by alternative algorithms such as Evolutionary, Particle Swarm Optimization or Harmony Search algorithms.     

Decentralized estimation and control of graph connectivity for mobile sensor networks

The ability of a robot team to reconfigure itself is useful in many applications: for metamorphic robots to change shape, for swarm motion towards a goal, for biological systems to avoid predators, or for mobile buoys to clean up oil spills. In many situations, auxiliary constraints, such as connectivity between team members or limits on the maximum hop-count, must be satisfied during reconfiguration. In this paper, we show that both the estimation and control of the graph connectivity can be accomplished in a decentralized manner. We describe a decentralized estimation procedure that allows each agent to track the algebraic connectivity of a time-varying graph. Based on this estimator, we further propose a decentralized gradient controller for each agent to maintain global connectivity during motion.     

A cellular learning automata-based deployment strategy for mobile wireless sensor networks

One important problem which may arise in designing a deployment strategy for a wireless sensor network is how to deploy a specific number of sensor nodes throughout an unknown network area so that the covered section of the area is maximized. In a mobile sensor network, this problem can be addressed by first deploying sensor nodes randomly in some initial positions within the area of the network, and then letting sensor nodes to move around and find their best positions according to the positions of their neighboring nodes. The problem becomes more complicated if sensor nodes have no information about their positions or even their relative distances to each other. In this paper, we propose a cellular learning automata-based deployment strategy which guides the movements of sensor nodes within the area of the network without any sensor to know its position or its relative distance to other sensors. In the proposed algorithm, the learning automaton in each node in cooperation with the learning automata in the neighboring nodes controls the movements of the node in order to attain high coverage. Experimental results have shown that in noise-free environments, the proposed algorithm can compete with the existing algorithms such as PF, DSSA, IDCA, and VEC in terms of network coverage. It has also been shown that in noisy environments, where utilized location estimation techniques such as GPS-based devices and localization algorithms experience inaccuracies in their measurements, or the movements of sensor nodes are not perfect and follow a probabilistic motion model, the proposed algorithm outperforms the existing algorithms in terms of network coverage.     

A stochastically constrained cellular model of urban growth

Recent approaches to modeling urban growth use the notion that urban development can be conceived as a self-organizing system in which natural constraints and institutional controls (land-use policies) temper the way in which local decision-making processes produce macroscopic patterns of urban form. In this paper a cellular automata (CA) model that simulates local decision-making processes associated with fine-scale urban form is developed and used to explore the notion of urban systems as self-organizing phenomenon. The CA model is integrated with a stochastic constraint model that incorporates broad-scale factors that modify or constrain urban growth. Local neighborhood access rules are applied within a broader neighborhood in which friction-of-distance limitations and constraints associated with socio-economic and bio-physical variables are stochastically realized. The model provides a means for simulating the different land-use scenarios that may result from alternative land-use policies. Application results are presented for possible growth scenarios in a rapidly urbanizing region in south east Queensland, Australia.     

A linear algorithm for the all-bidirectional-edges problem on planar graphs

The all-bidirectional-edges problem is to find an edge-labeling of an undirected networkG=(V, E), with a source and a sink, such that an edgee=uv inE is labeled u, v or u, u (or both) depending on the existence of a (simple) path from the source to the sink traversinge, that visits the verticesu andv in the orderu, v orv, u respectively. The best-known algorithm for this problem requiresO(¦V¦·¦E¦) time [5]. We show that the problem is solvable optimally on a planar graph.     

Incremental deployment of network monitors based on Group Betweenness Centrality

In many applications we are required to increase the deployment of a distributed monitoring system on an evolving network. In this paper we present a new method for finding candidate locations for additional deployment in the network. This method is based on the Group Betweenness Centrality (GBC) measure that is used to estimate the influence of a group of nodes over the information flow in the network. The new method assists in finding the location of k additional monitors in the evolving network, such that the portion of additional traffic covered is at least (1−1/e) of the optimal.     

A simple linear time certifying LBFS-based algorithm for recognizing trivially perfect graphs and their complements

We introduce a simple, linear time algorithm for recognizing trivially perfect (TP) graphs. It improves upon the algorithm of Yan et al. [J.-H. Yan, J.-J. Chen, G.J. Chang, Quasi-threshold graphs, Discrete Appl. Math. 69 (3) (1996) 247–255] in that it is certifying, producing a P₄ or a C₄ when the graph is not TP. In addition, our algorithm can be easily modified to recognize the complement of TP graphs (co-TP) in linear time as well. It is based on lexicographic BFS, and in particular the technique of partition refinement, which has been used in the recognition of many other graph classes [D.G. Corneil, Lexicographic breadth first search—a survey, in: WG 2004, in: Lecture Notes in Comput. Sci., vol. 3353, Springer, 2004, pp. 1–19].     

支持移动设备接入Gnutella网络的代理架构研究

针对当前移动设备无法加入Gnutella网络实现文件共享网络的现状,提出一种移动代理Gnutella网络架构的设计方案。利用移动代理作为移动设备的代理加入Gnutella网络,帮助移动设备实现文件的共享功能。架构能有效地减少移动设备的信息流量,并支持移动设备在Gnutella网络中实现可移动性。     

Model of the motion of agents with memory based on the cellular automaton

Abstract

The article is devoted to the construction of the motion model for agents with memory. Agents can be interpreted, for example, as mobile robots or soldiers. Agents move on the landscape consisting of squares with different passability. The model is based on the cellular automaton with one common to all agents layer corresponding to the landscape and many agent-specific layers corresponding to an agent’s memory. Methods for the random landscape generation are developed. The dependence between configuration entropy of the landscape, efficiency of the path-finding algorithm based on the cellular automaton was found. Also, the dependence of the average speed of the agents’ motion on the landscape configuration entropy was shown.     

一种适用于移动对等网络的分簇算法

通过分簇算法减小网络振动效应,延长网络的寿命是移动对等网络的研究重点之一。在研究Kautz图及其特性的基础上,提出一种基于Kautz图的移动对等网络分簇算法。在算法中,定义地址空间树,使用Kautz串作为节点标识,并运用后根序和宽度优先算法遍历地址空间树等一系列技术生成簇。同时设计了相关机制管理和维护簇结构,保证结构一致性。理论证明和实验评估表明,该分簇算法能有效减小振动效应,延长网络寿命。     

Characterizing the scale sensitivity of the cellular automata simulated urban growth: A case study of the Seberang Perai Region, Penang State, Malaysia

In modeling the complex behaviour of urban systems using a cellular automata approach, scale is an important concept in representing space since the result obtained at specific scale shall not be expected to be valid at another scale. The selection of scale, however, has often been taken for granted on the basis of information available to be mapped. Although it is desirable to run a model with fine spatial scale datasets, such datasets may well be costly to collect and add computational expenses in processing. This article investigates the effect of changing scale on the performance of a GIS-based cellular automata (CA) model developed to simulate the spatial pattern of urban growth. The sensitivity of scale of the input data used to parameterize the model was undertaken by evaluating the resulting prediction accuracy of the model and the morphology of urban areas. It seemed that the model managed to perform well and produce realistic urban form only up to specific range of scale. Thus, the selection of scale to represent urban system under consideration has to be undertaken with care, in order to ensure that the output produced maintains the overall accuracy of the model and morphology of urban areas.     

A linear time algorithm for finding an optimal degree-bounded subtree of an edge-weighted tree

Given an edge-weighted tree T=(V(T),E(T)) and its subtree T^′, for any v∈V(T), the distance d(v,T^′) is defined as the minimum weighted distance from v to any vertex in T^′. The distance d(T,T^′) is defined as the sum of all distances of the form d(v,T^′) where v∈V(T). We give an algorithm to find a T^′ that minimizes d(T,T^′) and for all w∈V(T^′), the degree degT^′(w) of w is not more than a prespecified bound db(w)(0?db(w)?degT(w)) at w. The worst-case running time of our algorithm is in O(|V(T)|).     

A faster parametric minimum-cut algorithm

Galloet al. [4] recently examined the problem of computing on line a sequence ofk maximum flows and minimum cuts in a network ofn nodes, where certain edge capacities change between each flow. They showed that for an important class of networks, thek maximum flows and minimum cuts can be computed simply in O(n³+kn²) total time, provided that the capacity changes are made in order. Using dynamic trees their time bound isO(nm log(n²/m)+km log(n²/m)). We show how to reduce the total time, using a simple algorithm, to O(n³+kn) for explicitly computing thek minimum cuts and implicitly representing thek flows. Using dynamic trees our bound is O(nm log(n²/m)+kn log(n²/m)). We further reduce the total time toO(n ²m) ifk is at most O(n). We also apply the ideas from [10] to show that the faster bounds hold even when the capacity changes are not in order, provided we only need the minimum cuts; if the flows are required then the times are respectively O(n³+km) and O(n²m). We illustrate the utility of these results by applying them to therectilinear layout problem.The research of Dan Gusfield was partially supported by Grants CCR-8803704 and CCR-9103937 from the National Science Foundation. The research of Éva Tardos was partially supported by a David and Lucile Packard Fellowship, an NSF Presidential Young Investigator Fellowship, a Research Fellowship of the Sloan Foundation, and by NSF, DARPA, and ONR through Grant DMS89-20550 from the National Science Foundation.     

优化网络生命周期和最短化路径的WSN移动sink路径规划算法

为了缓解无线传感器网络（WSN）中传感器节点分布不均匀、传感器节点感知数据量不同而造成能耗不均衡、"热区"等问题,提出一种优化网络生命周期和最短化路径的WSN移动sink路径规划算法（MSPPA）。首先,通过监测区域网格化,在每个网格内分布若干个移动sink候选访问站点,sink在每个网格中选择一个站点停留收集网格中节点数据;然后,分析所有传感器节点的生命周期与sink站点选择的关系,建立权衡网络生命周期和sink移动路径的优化模型;最后,使用双链遗传算法规划移动sink遍历网格的顺序和选择每个网格中移动sink访问站点,得到移动sink节点遍历所有网格收集数据的路径。仿真结果显示,与已有的低功耗自适应分簇（LEACH）算法与基于移动sink节点与集合节点（RN）的优化LEACH分簇算法（MS-LEACH-RN）相比,MSPPA在网络生命周期方面提高了60%,且具有良好的能耗均衡性。实验结果表明,MSPPA能有效缓解能量不均衡、"热区"问题,延长网络生命周期。