Choco Banana is one of Nikoli’s pencil puzzles. We study the computational complexity of Choco Banana. It is shown that deciding whether a given instance of the Choco Banana puzzle has a solution is NP-complete.

As a hierarchical network framework, clustering aims to divide nodes with similar mobility characteristics into the same cluster to form a more structured hierarchical network, which can effectively solve the problem of high dynamics of the network topology caused by the high-speed movement of nodes in aeronautical ad hoc networks. Based on this goal, we propose a multi-hop distributed clustering algorithm based on link duration. The algorithm is based on the idea of multi-hop clustering, which ensures the coverage and stability of clustering. In the clustering phase, the link duration is used to accurately measure the degree of stability between nodes. At the same time, we also use the link duration threshold to filter out relatively stable links and use the gravity factor to let nodes set conditions for actively creating links based on neighbor distribution. When selecting the cluster head, we select the most stable node as the cluster head node based on the defined node stability weight. The node stability weight comprehensively considers the connectivity degree of nodes and the link duration between nodes. In order to verify the effectiveness of the proposed method, we compare them with the N-hop and K-means algorithms from four indicators: average cluster head duration, average cluster member duration, number of cluster head changes, and average number of intra-cluster link changes. Experiments show that the proposed method can effectively improve the stability of the topology.

A drone swarm is a robotic architecture having multiple drones cooperate to accomplish a mission. Nowadays, heterogeneous drone swarms, in which a small number of gateway drones (GWs) act as protocol translators to enable the mixing of multiple swarms that use independent wireless protocols, have attracted much attention from many researchers. Our previous work proposed Path Optimizer — a method to minimize the number of end-to-end path-hops in a remote video monitoring system using heterogeneous drone swarms by autonomously relocating GWs to create a shortcut in the network for each communication request. However, Path Optimizer has limitations in improving communication quality when more video sessions than the number of GWs are requested simultaneously. Path Coordinator, which we propose in this paper, achieves a uniform reduction in end-to-end hops and maximizes the allowable hop satisfaction rate regardless of the number of sessions by introducing the cooperative and synchronous relocation of all GWs. Path Coordinator consists of two phases: first, physical optimization is performed by geographically relocating all GWs (relocation phase), and then logical optimization is achieved by modifying the relaying GWs of each video flow (rerouting phase). Computer simulations reveal that Path Coordinator adapts to various environments and performs as well as we expected. Furthermore, its performance is comparable to the upper limits possible with brute-force search.

Currently, NDN-based VANETs protocols have several problems with packet overhead of rebroadcasting, control packet, and the accuracy of next-hop selection due to the dynamic topology. To deal with these problems in this paper, we propose a robust and lightweight forwarding protocol in Vehicular ad-hoc Named Data Networking. The concept of our forwarding protocol is adopting a packet-free approach. A vehicle collects its neighbor's visual identification by a pair of cameras (front and rear) to assign a unique visual ID for each node. Based on these IDs, we construct a hop-by-hop FIB-based forwarding strategy effectively. Furthermore, the Face duplication [1] in the wireless environment causes an all-broadcast problem. We add the visual information to Face to distinguish the incoming and outgoing Face to prevent broadcast-storm and make FIB and PIT work more accurate and efficiently. The performance evaluation results focusing on the communication overhead show that our proposal has better results in overall network traffic costs and Interest satisfaction ratio than previous works.

In this study, we consider fake message attacks in sparse mobile ad hoc networks, in which nodes are chronically isolated. In these networks, messages are delivered to their destination nodes using store-carry-forward routing, where they are relayed by some nodes. Therefore, when a node has messages in its buffer, it can falsify the messages easily. When malicious nodes exist in the network, they alter messages to create fake messages, and then they launch fake message attacks, that is, the fake messages are spread over the network. To analyze the negative effects of a fake message attack, we model the system dynamics without attack countermeasures using a Markov chain, and then formalize some performance metrics (i.e., the delivery probability, mean delivery delay, and mean number of forwarded messages). This analysis is useful for designing countermeasures. Moreover, we consider a hash-based countermeasure against fake message attacks using a hash of the message. Whenever a node that has a message and its hash encounters another node, it probabilistically forwards only one of them to the encountered node. By doing this, the message and the hash value can be delivered to the destination node via different relay nodes. Therefore, even if the destination node receives a fake message, it can verify the legitimacy of the received message. Through simulation experiments, we evaluate the effectiveness of the hash-based countermeasure.

Heterogeneous drone swarms are large hybrid drone clusters in which multiple drones with different wireless protocols are interconnected by some translator drones called GWs. Nowadays, because inexpensive drones, such as toy drones, have become widely used in society, the technology for constructing huge drone swarms is attracting more and more attention. In this paper, we propose an autonomous GW mobility control algorithm for establishing stabilized and low-delay communication among heterogeneous clusters, assuming that only GWs are controllable and relocatable to ensure the flexible operationality of drone swarms. Our proposed algorithm is composed of two independent sub algorithms - the Link Stabilizer and the Path Optimizer. The Stabilizer maintains the neighbor links and consists of two schemes: the neighbor clustering based on relative velocities and the GW velocity calculation using a kinetic model. The Optimizer creates a shortcut to reduce the end-to-end delay for newly established communication by relocating the GW dynamically. We also propose a conceptual protocol design to implement this algorithm into real-world drone swarms in a distributed manner. Computer simulation reveals that the Stabilizer improved the connection stability for all three mobility models even under the high node mobility, and the Optimizer reduced the communication delay by the optimal shortcut formation under any conditions of the experiments and its performance is comparable to the performance upper limit obtained by the brute-force searching.

In wireless multi-hop networks such as ad hoc networks and sensor networks, backoff-based opportunistic routing protocols, which make a forwarding decision based on backoff time, have been proposed. In the protocols, each potential forwarder calculates the backoff time based on the product of a weight and global scaling factor. The weight prioritizes potential forwarders and is calculated based on hop counts to the destination of a sender and receiver. The global scaling factor is a predetermined value to map the weight to the actual backoff time. However, there are three common issues derived from the global scaling factor. First, it is necessary to share the predetermined global scaling factor with a centralized manner among all terminals properly for the backoff time calculation. Second, it is almost impossible to change the global scaling factor during the networks are being used. Third, it is difficult to set the global scaling factor to an appropriate value since the value differs among each local surrounding of forwarders. To address the aforementioned issues, this paper proposes a novel decentralized local scaling factor control without relying on a predetermined global scaling factor. The proposed method consists of the following three mechanisms: (1) sender-centric local scaling factor setting mechanism in a decentralized manner instead of the global scaling factor, (2) adaptive scaling factor control mechanism which adapts the local scaling factor to each local surrounding of forwarders, and (3) mitigation mechanism for excessive local scaling factor increases for the local scaling factor convergence. Finally, this paper evaluates the backoff-based opportunistic routing protocol with and without the proposed method using computer simulations.

This paper proposes a novel interaction technique to transfer data across various types of digital devices in uniform a manner and to allow specifying what kind of data should be sent. In our framework, when users tap multiple devices rhythmically, data corresponding to the rhythm (transfer type) are transferred from a device tapped in the first tap (source device) to the other (target device). It is easy to operate, applicable to a wide range of devices, and extensible in a sense that we can adopt new transfer types by adding new rhythms. Through a subjective evaluation and a simulation, we had a prospect that our approach would be feasible. We also discuss suggestions and limitation to implement the technique.

This paper studies the problem of real-time routing in a multi-autonomous robot enhanced network at uncertain and vulnerable tactical edge. Recent network protocols, such as opportunistic mobile network routing protocols, engaged social network in communication network that can increase the interoperability by using social mobility and opportunistic carry and forward routing algorithms. However, in practical harsh environment such as a battlefield, the uncertainty of social mobility and complexity of vulnerable environment due to unpredictable physical and cyber-attacks from enemy, would seriously affect the effectiveness and practicality of these emerging network protocols. This paper presents a GT-SaRE-MANET (Game Theoretic Situation-aware Robot Enhanced Mobile Ad-hoc Network) routing protocol that adopt the online reinforcement learning technique to supervise the mobility of multi-robots as well as handle the uncertainty and potential physical and cyber attack at tactical edge. Firstly, a set of game theoretic mission oriented metrics has been introduced to describe the interrelation among network quality, multi-robot mobility as well as potential attacking activities. Then, a distributed multi-agent game theoretic reinforcement learning algorithm has been developed. It will not only optimize GT-SaRE-MANET routing protocol and the mobility of multi-robots online, but also effectively avoid the physical and/or cyber-attacks from enemy by using the game theoretic mission oriented metrics. The effectiveness of proposed design has been demonstrated through computer aided simulations and hardware experiments.

In this paper, we propose a new routing protocol for named data networking applied to ad hoc networks. We suppose a type of ad hoc networks that advertise versatile information in public spaces such as shopping mall and museum. In this kind of networks, information providers prepare fixed nodes, and users are equipped with mobile terminals. So, we adopt a hybrid approach where a proactive routing is used in the producer side network and a reactive routing is used in the consumer side network. Another feature of the proposed protocol is that only the name prefix advertisement is focused on in the proactive routing. The result of performance evaluation focusing on the communication overhead shows that our proposal has a moderate overhead both for routing control messages and Interest packets compared with some of conventional NDN based ad hoc routing mechanisms proposed so far.

Cooperative communication can reduce energy consumption effectively due to its superior diversity gain. To further prolong network lifetime and improve the energy efficiency, this paper studies energy-efficient packet transmission in wireless ad-hoc networks and proposes a novel cluster-based cooperative packet transmission (CCPT) protocol to mitigate the packet loss and balance the energy consumption of networks. The proposed CCPT protocol first constructs a highly energy-efficient initial routing path based on the required energy cost of non-cooperative transmission. Then an iterative cluster recruitment algorithm is proposed that selects cooperative nodes and organizing them into clusters, which can create transmit diversity in each hop of communication. Finally, a novel two-step cluster-to-cluster cooperative transmission scheme is designed, where all cluster members cooperatively forward the packet to the next-hop cluster. Simulation results show that the CCPT protocol effectively reduces the energy cost and prolongs the network lifetime compared with the previous CwR and noC schemes. The results also have shown that the proposed CCPT protocol outperforms the traditional CwR protocol in terms of transmit efficiency per energy, which indicates that CCPT protocol has achieved a better trade-off between energy and packet arrival ratio.

To minimize the damage caused by landslides resulting from torrential rain, residents must quickly evacuate to a place of refuge. To make the decision to evacuate, residents must be able to collect and share disaster information. Firstly, this paper introduces the Grass-roots Information Distribution System and a fixed type monitoring system which our research group has been developing. The fixed type monitoring system is deployed at the location of apparent danger, whereas the Grass-roots Information Distribution System distributes disaster information acquired from the fixed type monitoring system through a mobile ad hoc network (MANET) to residents. The MANET is configured using mobile terminals of residents. Next, in this paper, an information dissemination scheme utilizing a MANET and cellular networks to communicate among mobile terminals is proposed and simulated in the area where our research group has been deploying the distribution system. The MANET topology and information distribution obtained from the simulation results for further field experiments are then discussed.

Maximal designed distances for nonbinary narrow-sense quantum Bose-Chaudhuri-Hocquenghem (BCH) codes of length $n=rac{q^4-1}{r}$ and new constructions for them are given, where q is an odd prime power. These constructions are capable of designing quantum BCH codes with new parameters. Furthermore, some codes obtained here have better parameters than those constructed by other known constructions.

The integration of VANETs with Internet is required if vehicles are to access IP-based applications. A vehicle must have an IP address, and the IP mobility service should be supported during the movement of the vehicle. VANET standards such as WAVE or C-ITS use IPv6 address auto configuration to allocate an IP address to a vehicle. In C-ITS, NEMO-BS is used to support IP mobility. The vehicle moves rapidly, so reallocation of IP address as well as binding update occurs frequently. The vehicle' communication, however, may be disrupted for a considerable amount of time, and the packet loss occurs during these events. Also, the finding of the home address of the peer vehicle is not a trivial matter. We propose a network based identifier locator separation scheme for VANETs. The scheme uses a vehicle identity based address generation scheme. It eliminates the frequent address reallocation and simplifies the finding of the peer vehicle IP address. In the scheme, a network entity tracks the vehicles in its coverage and the vehicles share the IP address of the network entity for their locators. The network entity manages the mapping between the vehicle's identifier and its IP address. The scheme excludes the vehicles from the mobility procedure, so a vehicle needs only the standard IPv6 protocol stack, and mobility signaling does not occur on the wireless link. The scheme also supports seamlessness, so packet loss is mitigated. The results of a simulation show that the vehicles experience seamless packet delivery.

Wireless Ad hoc networks have been rapidly developed in recent years since they promise a wide range of applications. However, their structures, which are based on the IEEE 802.11 standard, cause a severe unfairness problem in bandwidth sharing among different users. This is an extreme drawback because in wireless ad hoc networks, all users need to be treated fairly regardless of their geographical positions. In this paper, we propose a method to improve the fairness among flows by sensing channel access of other nodes based on the information obtained at the link layer and then, controlling the packet sending rate from the link layer to the MAC layer and the dequeue rate from the queue. Simulation results show that the proposed method achieves a better fairness with a good total throughput compared to conventional methods.

From past experience of the large-scale cutoff of existing networks as a result of the East Japan Great Earthquake and tsunamis, and from previous research on stabilizing ad hoc networks that lack control mechanisms, we have strengthened the resilience of NerveNet. NerveNet was originally designed and developed as an access network for providing context-aware services with the use of sensors and actuators. Thus, at present, it has the capability to enable resilient information sharing and communications in a region even if access to the Internet is impossible in emergency situations. NerveNet is composed of single or multiple base stations interconnected by a variety of Ethernet-based wired or wireless transmission systems. A network is formed using line, star, tree, or mesh topology. Network and data management works in each base station in a distributed manner, resulting in the resilience of this system. In collaboration with the town of Shirahama in Wakayama prefecture in Japan, we have been conducting a pilot test with the NerveNet testbed. The test includes nine base stations interconnected by 5.6-GHz Wi-Fi and Fixed Wireless Access (FWA), providing tourists and residents with Internet access. In the future, we expect that not only NerveNet but also other novel technologies will contribute to solving social problems and enriching people's lives.

In this paper, MWAN (Mobile Wireless Ad hoc Networks with internet connection) is considered, which is a solution for many tasks owing to its ease of use, and practicality. Recently, MWAN is required to support large data like multimedia data transfer and it is transferred through several relay nodes. There are 2 problems that cause difficulties for large data transfer through a mobile network. First one is rerouting delay by handoff and second one is network congestion caused by handoff. Also, faulty data transfer caused by handoff delay makes extra load and causes some problems for MWAN. To solve these problems and get network reliability, we propose a new multipath routing scheme that can provide solution for seamless connection while handoff. In the proposed scheme, our MWAN can support multiple paths for data transfer, maintain end-to-end connection while handoff and get new route quickly. The performance of the proposed scheme is evaluated and compared with other multipath routing scheme to show the improvement.

Personalized PageRank (PPR) is a typical similarity metric between nodes in a graph, and node searches based on PPR are widely used. In many applications, graphs change dynamically, and in such cases, it is desirable to perform ad hoc searches based on PPR. An ad hoc search involves performing searches by varying the search parameters or graphs. However, as the size of a graph increases, the computation cost of performing an ad hoc search can become excessive. In this paper, we propose a method called Castanet that offers fast ad hoc searches of PPR. The proposed method features (1) iterative estimation of the upper and lower bounds of PPR scores, and (2) dynamic pruning of nodes that are not needed to obtain a search result. Experiments confirm that the proposed method does offer faster ad hoc PPR searches than existing methods.

We propose the node name routing (NNR) strategy for information-centric ad-hoc networks based on the named-node networking (3N). This strategy is especially valuable for use in disaster areas because, when the Internet is out of service during a disaster, our strategy can be used to set up a self-organizing network via cell phones or other terminal devices that have a sharing ability, and it does not rely on a base station (BS) or similar providers. Our proposed strategy can solve the multiple-name problem that has arisen in prior 3N proposals, as well as the dead loop problems in both 3N ad-hoc networks and TCP/IP ad-hoc networks. To evaluate the NNR strategy, it is compared with the optimized link state routing protocol (OLSR) and the dynamic source routing (DSR) strategy. Computer-based comprehensive simulations showed that our NNR proposal exhibits a better performance in this environment when all of the users are moving randomly. We further observed that with a growing number of users, our NNR protocol performs better in terms of packet delivery, routing cost, etc.

We propose a QoS scheme for ad hoc networks by combining TDMA and IEEE 802.11 DCF, and present performance evaluation results of the scheme. In the proposed scheme, the channel time is composed of two different periods, specifically TDMA period and DCF period. The TDMA period provides contention free transmission opportunities for QoS flows, and the DCF period provides contention-based access for best effort or low priority flows. We evaluate the proposed scheme for various numbers of TCP flows and different CBR data rates with QualNet simulator. Simulation results show that the protocol is able to provide an efficient solution for QoS control in ad hoc networks.