In this paper we study a recently proposed variant of the r-gathering problem. An r-gathering of customers C to facilities F is an assignment A of C to open facilities F' ⊂ F such that r or more customers are assigned to each open facility. (Each facility needs enough number of customers to open.) Given an opening cost op(f) for each f∈F, and a connecting cost co(c,f) for each pair of c∈C and f∈F, the cost of an r-gathering A is max{maxc∈C{co(c, A(c))}, maxf∈F'{op(f)}}. The r-gathering problem consists of finding an r-gathering having the minimum cost. Assume that F is a set of locations for emergency shelters, op(f) is the time needed to prepare a shelter f∈F, and co(c,f) is the time needed for a person c∈C to reach assigned shelter f=A(c)∈F. Then an r-gathering corresponds to an evacuation plan such that each open shelter serves r or more people, and the r-gathering problem consists of finding an evacuation plan minimizing the evacuation time span. However in a solution above some person may be assigned to a farther open shelter although it has a closer open shelter. It may be difficult for the person to accept such an assignment for an emergency situation. Therefore, Armon considered the problem with one more additional constraint, that is, each customer should be assigned to a closest open facility, and gave a 9-approximation polynomial-time algorithm for the problem. We have designed a simple 3-approximation algorithm for the problem. The running time is O(r|C||F|).

Event detection and recognition are important for environmental monitoring in the Internet of things and cyber-physical systems. Low power wide area (LPWA) networks are one of the most powerful wireless sensor networks to support data gathering; however, they do not afford peak wireless access from sensors that detect significant changes in sensing data. Various data gathering schemes for event detection and recognition have been proposed. However, these do not satisfy the requirement for the three functions for the detection of the occurrence of an event, the recognition of the position of an event, and the recognition of spillover of impact from an event. This study proposes a three-stage data gathering scheme for LPWA. In the first stage, the access limitation based on the comparison between the detected sensing data and the high-level threshold is effective in reducing the simultaneous accessing sensors; thus, high-speed recognition of the starting event is achieved. In the second stage, the data centre station designates the sensor to inform the sensing data to achieve high accuracy of the position estimation of the event. In the third stage, all the sensors, except for the accessing sensors in the early stage, access the data centre. Owing to the exhaustive gathering of sensing data, the spillover of impact from the event can be recognised with high accuracy. We implement the proposed data gathering scheme for the actual wireless sensor system of the LPWA. From the computer simulation and experimental evaluation, we show the advantage of the proposed scheme compared to the conventional scheme.

We study the gathering problem requiring a team of mobile agents to gather at a single node in arbitrary networks. The team consists of k agents with unique identifiers (IDs), and f of them are weakly Byzantine agents, which behave arbitrarily except falsifying their identifiers. The agents move in synchronous rounds and cannot leave any information on nodes. If the number of nodes n is given to agents, the existing fastest algorithm tolerates any number of weakly Byzantine agents and achieves gathering with simultaneous termination in O(n4·|Λgood|·X(n)) rounds, where |Λgood| is the length of the maximum ID of non-Byzantine agents and X(n) is the number of rounds required to explore any network composed of n nodes. In this paper, we ask the question of whether we can reduce the time complexity if we have a strong team, i.e., a team with a few Byzantine agents, because not so many agents are subject to faults in practice. We give a positive answer to this question by proposing two algorithms in the case where at least 4f2+9f+4 agents exist. Both the algorithms assume that the upper bound N of n is given to agents. The first algorithm achieves gathering with non-simultaneous termination in O((f+|&Lambdagood|)·X(N)) rounds. The second algorithm achieves gathering with simultaneous termination in O((f+|&Lambdaall|)·X(N)) rounds, where |&Lambdaall| is the length of the maximum ID of all agents. The second algorithm significantly reduces the time complexity compared to the existing one if n is given to agents and |&Lambdaall|=O(|&Lambdagood|) holds.

Data aggregation trees in wireless sensor networks (WSNs) are being used for gathering data for various purposes. Especially for the trees within buildings or civil structures, the total amount of energy consumption in a tree must be reduced to save energy. Therefore, the minimum energy-cost aggregation tree (MECAT) and MECAT with relay nodes (MECAT_RN) problems are being discussed to reduce energy consumption in data aggregation trees in WSNs. This paper proposes the tree node switching algorithm (TNSA) that improves on the previous algorithms for the MECAT and MECAT_RN problems in terms of energy efficiency. TNSA repeatedly switches nodes in a tree to reduce the number of packets sent in the tree. Packets are reduced by improving the accommodation efficiency of each packet, in which multiple sensor reports are accommodated. As a result of applying TNSA to MECATs and MECAT-RNs, energy consumption can be reduced significantly with a small burden.

We propose two algorithms for the gathering of k mobile agents in asynchronous Byzantine environments. For both algorithms, we assume that graph topology is arbitrary, each node is equipped with an authenticated whiteboard, agents have unique IDs, and at most f weakly Byzantine agents exist. Here, a weakly Byzantine agent can make arbitrary behavior except falsifying its ID. Under these assumptions, the first algorithm achieves a gathering without termination detection in O(m+fn) moves per agent (m is the number of edges and n is the number of nodes). The second algorithm achieves a gathering with termination detection in O(m+fn) moves per agent by additionally assuming that agents on the same node are synchronized, $f

Sensor-data gathering using multi-hop connections in a wireless sensor network is being widely used, and a tree topology for data gathering is considered promising because it eases data aggregation. Therefore, many sensor-tree-creation algorithms have been proposed. The sensors in a tree, however, generally run on batteries, so long tree lifetime is one of the most important factors in collecting sensor data from a tree over a long period. It has been proven that creating the longest-lifetime tree is a non-deterministic-polynomial complete problem; thus, all previously proposed sensor-tree-creation algorithms are heuristic. To evaluate a heuristic algorithm, the time complexity of the algorithm is very important, as well as the quantitative evaluation of the lifetimes of the created trees and algorithm speed. This paper proposes an algorithm called assured switching with accurate graph optimization (ASAGAO) that can create a sensor tree with a much longer lifetime much faster than other sensor-tree-creation algorithms. In addition, it has much smaller time complexity.

In this paper, we consider the partial gathering problem of mobile agents in arbitrary networks. The partial gathering problem is a generalization of the (well-investigated) total gathering problem, which requires that all the agents meet at the same node. The partial gathering problem requires, for a given positive integer g, that each agent should move to a node and terminate so that at least g agents should meet at each of the nodes they terminate at. The requirement for the partial gathering problem is no stronger than that for the total gathering problem, and thus, we clarify the difference on the move complexity between them. First, we show that agents require Ω(gn+m) total moves to solve the partial gathering problem, where n is the number of nodes and m is the number of communication links. Next, we propose a deterministic algorithm to solve the partial gathering problem in O(gn+m) total moves, which is asymptotically optimal in terms of total moves. Note that, it is known that agents require Ω(kn+m) total moves to solve the total gathering problem in arbitrary networks, where k is the number of agents. Thus, our result shows that the partial gathering problem is solvable with strictly fewer total moves compared to the total gathering problem in arbitrary networks.

We have proposed a fish farm monitoring system for achieving efficient fish farming. In our system, sensor nodes are attached at fish to monitor its health status. In this letter, we propose a method for gathering sensor data from sensor nodes to sink nodes when the transmission range of sensor node is shorter than the size of fish cage. In our proposed method, a part of sensor nodes become leader nodes and they forward gathered sensor data to the sink nodes. Through simulation evaluations, we show that the data gathering performance of our proposed method is higher than that of traditional methods.

The abnormal crowd behavior detection is an important research topic in computer vision to improve the response time of critical events. In this letter, we introduce a novel method to detect and localize the crowd gathering in surveillance videos. The proposed foreground stillness model is based on the foreground object mask and the dense optical flow to measure the instantaneous crowd stillness level. Further, we obtain the long-term crowd stillness level by the leaky bucket model, and the crowd gathering behavior can be detected by the threshold analysis. Experimental results indicate that our proposed approach can detect and locate crowd gathering events, and it is capable of distinguishing between standing and walking crowd. The experiments in realistic scenes with 88.65% accuracy for detection of gathering frames show that our method is effective for crowd gathering behavior detection.

We propose an algorithm for the gathering problem of mobile agents in arbitrary networks (graphs) with Byzantine agents. Our algorithm can make all correct agents meet at a single node in O(fm) time (f is the upper bound of the number of Byzantine agents and m is the number of edges) under the assumption that agents have unique ID and behave synchronously, each node is equipped with an authenticated whiteboard, and f is known to agents. Here, the whiteboard is a node memory where agents can leave information. Since the existing algorithm achieves gathering without a whiteboard in Õ(n9λ) time, where n is the number of nodes and λ is the length of the longest ID, our algorithm shows an authenticated whiteboard can significantly reduce the time for the gathering problem in Byzantine environments.

We have proposed a fish farm monitoring system for the efficient farming of tuna. In our system, energy efficient and adaptive control of sensor node is highly important. In addition, since a sensor node is attached to the fish, the transmission range of sensor node is not omni-directional. In this paper, we propose a data gathering mechanism for fish farm monitoring by extending a traditional desyncronization mechanism. In our proposed mechanism, by utilizing acknowledgment packets from the sink node, distributed and adaptive timing control of packet transmission is accomplished. In addition, we apply a reassignment mechanism and a sleep mechanism for improving the performance of our proposed mechanism. Through simulation experiments, we show that the performance of our proposed mechanism is higher than that of comparative mechanisms.

As autonomous underwater vehicles (AUVs) have been widely used to perform cooperative works with sensor nodes for data-gathering, the need for long-range AUVs has further grown to support the long-duration cooperation with sensor nodes. However, as existing data-gathering protocols for the cooperative works have not considered AUVs' energy consumption, AUVs can deplete their energy more quickly before fulfilling their missions. The objective of this work is to develop an AUV based data-gathering protocol that maximizes the duration for the cooperative works. Simulation results show that the proposed protocol outperforms existing protocols with respect to the long-range AUVs.

Recently, the growing concepts that information communication technologies apply to social infrastructures have caused deep interests with wireless sensor networks (WSNs). WSNs can be used for various application areas such as home, health, factory and so on. For the different application areas, there are different technical issues (e.g., security, reliability, real time gathering, long life time, scalability). Efficient information gathering can be potentially obtained if we take a suitable information gathering method with considering the requirements of each WSN application. Thus, we have not persisted all information gathering perfectly and have proposed one of simple information gathering methods in response to the requirements of WSN applications in this paper. In the proposed method, the information is converted to physical-layer parameters of wireless communications, such as frequency and time. Also, simulations are performed to validate the effectiveness of the proposed method in real time gathering and estimating with high precision.

In this letter, a distributed TDMA-based data gathering scheme for wireless sensor networks, called DTDGS, is proposed in order to avoid transmission collisions, achieve high levels of power conservation and improve network lifetime. Our study is based on corona-based network division and a distributed TDMA-based scheduling mechanism. Different from a centralized algorithm, DTDGS does not need a centralized gateway to assign the transmission time slots and compute the route for each node. In DTDGS, each node selects its transmission slots and next-hop forwarding node according to the information gathered from neighbor nodes. It aims at avoiding transmission collisions and balancing energy consumption among nodes in the same corona. Compared with previous data gathering schemes, DTDGS is highly scalable and energy efficient. Simulation results show high the energy efficiency of DTDGS.

The gathering problem of anonymous and oblivious mobile robots is one of the fundamental problems in the theoretical mobile robotics. We consider the gathering problem in unoriented and anonymous rings, which requires that all robots eventually keep their positions at a common non-predefined node. Since the gathering problem cannot be solved without any additional capability to robots, all the previous results assume some capability of robots, such as the agreement of local view. In this paper, we focus on the multiplicity detection capability. This paper presents a deterministic gathering algorithm with local-weak multiplicity detection, which provides a robot with information about whether its current node has more than one robot or not. This assumption is strictly weaker than that in previous works. Our algorithm achieves the gathering from an aperiodic and asymmetric configuration with 2 < k < n/2 robots, where n is the number of nodes. We also show that our algorithm is asymptotically time-optimal one, i.e., the time complexity of our algorithm is O(n). Interestingly, despite the weaker assumption, it achieves significant improvement compared to the previous algorithm, which takes O(kn) time for k robots.

Many methods have been researched to prolong the lifetime of sensor networks that use mobile technologies. In the mobile sink research, there are the track based methods and the anchor points based methods as representative operation methods for mobile sinks. However, most existing methods decrease the Quality of Service (QoS) and lead to routing hotspots in the vicinity of the mobile sinks. The main reason is that they use static mobile sink movement paths that ignore the network environment such as the query position and the data priority. In this paper, we propose a novel mobile sink operation method that solves the problems of the existing methods. In our method, the probe priority of the mobile sink is determined from data priority to increase the QoS. The mobility of sink used to reduce the routing hotspot. Experiments show that the proposed method reduces the query response time and improves the network lifetime much more than the existing methods.

This paper presents a prototype group modem for a hyper-multipoint data gathering satellite communication system. It can handle arbitrarily and dynamically assigned FDMA signals by employing a novel FFT-type block demultiplexer/multiplexer. We clarify its configuration and operational principle. Experiments show that the developed modem offers excellent performance.

This paper describes a novel channel allocation scheme that enables data to be collected from observation points throughout the ultra-wide area covered by a satellite communication system. Most of the earth stations in the system acquire pre-scheduled type data such as that pertaining to rainfall and temperature measurements, but a few of them acquire event-driven type data such as that pertaining to earthquakes. Therefore, the main issue pertaining to this scheme is how to effectively accommodate demand for the channels by a huge number of earth stations with limited satellite frequency bandwidth regardless of their acquired data types. To tackle this issue, we propose a channel allocation scheme built on a pre-assigned scheme to gather pre-scheduled type data but that also includes an additional procedure to gather event-driven type data reliably. Performance evaluations show that the proposed scheme achieves higher throughput and lower packet loss rate than conventional schemes.

Wireless sensor networks (WSNs) have attracted a significant amount of interest from many researchers because they have great potential as a means of obtaining information of various environments remotely. WSNs have a wide range of applications, such as natural environmental monitoring in forest regions and environmental control in office buildings. In WSNs, hundreds or thousands of micro-sensor nodes with such resource limitations as battery capacity, memory, CPU, and communication capacity are deployed without control in a region and used to monitor and gather sensor information of environments. Therefore, a scalable and efficient network control and/or data gathering scheme for saving energy consumption of each sensor node is needed to prolong WSN lifetime. In this paper, assuming that sensor nodes synchronize to intermittently communicate with each other only when they are active for realizing the long-term employment of WSNs, we propose a new synchronization scheme for gathering sensor information using chaotic pulse-coupled neural networks (CPCNN). We evaluate the proposed scheme using computer simulations and discuss its development potential. In simulation experiments, the proposed scheme is compared with a previous synchronization scheme based on a pulse-coupled oscillator model to verify its effectiveness.

One challenging issue of sensor networks is extension of overall network system lifetimes. In periodic data gathering applications, the typical sensor node spends more time in the idle state than active state. Consequently, it is important to decrease power consumption during idle time. In this study, we propose a scheduling scheme based on the history of RTS/CTS exchange during the setup phase. Scheduling the transmission during transfer phase enables each node to turn off its RF circuit during idle time. By tracing ongoing RTS/CTS exchange during the steady phase, each node knows the progress of the data transfer process. Thereby, it can wait to receive packets for data aggregation. Simulation results show a 160-260% longer system lifetime with the proposed scheduling scheme compared to the existing approaches.