The broadcast scheduling problem (BSP) in wireless ad-hoc networks is a well-known NP-complete combinatorial optimization problem. The BSP aims at finding a transmission schedule whose time slots are collision free in a wireless ad-hoc network with time-division multiple access (TDMA). The transmission schedule is optimized for minimizing the frame length of the node transmissions and maximizing the utilization of the shared channel. Recently, many metaheuristics can optimally solve smaller problem instances of the BSP. However, for complex problem instances, the computation of metaheuristics can be quite time and memory consuming. In this work, we propose a greedy genetic algorithm for solving the BSP with a large number of nodes. We present three heuristic genetic operators, including a greedy crossover and two greedy mutation operators, to optimize both objectives of the BSP. These heuristic genetic operators can generate good solutions. Our experiments use both benchmark data sets and randomly generated problem instances. The experimental results show that our genetic algorithm is effective in solving the BSP problem instances of large-scale networks with 2,500 nodes.

Data caching is widely known as an effective power-saving technique, in which mobile devices use local caches instead of original data placed on a server, in order to reduce the power consumption necessary for network accesses. In such data caching, a cache invalidation mechanism is important in preventing these devices from unintentionally accessing invalid data. In this paper, we propose a broadcast-based protocol for cache invalidation in a location-aware system. The proposed protocol is designed to reduce the access time required for obtaining necessary invalidation reports through broadcast media and to avoid client-side sleep fragmentation while retrieving the reports. In the proposed protocol, a Bloom filter is used as the data structure of an invalidation report, in order to probabilistically check the invalidation of caches. Furthermore, we propose three broadcast scheduling methods that are intended to achieve flexible broadcasting structured by the Bloom filter: fragmentation avoidance scheduling method (FASM), metrics balancing scheduling method (MBSM), and minimizing access time scheduling method (MASM). The broadcast schedule is arranged for consecutive accesses to geographically neighboring invalidation reports. In addition, the effectiveness of the proposed methods is evaluated by simulation. The results indicate that the MBSM and MASM achieve a high rate of performance scheduling. Compared to the FASM, the MBSM reduces the access time by 34%, while the fragmentations on the resultant schedule increase by 40%, and the MASM reduces the access time by 40%, along with an 85% increase in the number of fragmentations.

For wireless sensor networks in which resources are limited and network topology dynamically changes, we propose the one-hop neighbor based broadcast scheduling (ONBS) algorithm to provide reliable delivery service of broadcast packets. The proposed algorithm reduces the scheduling overhead by allowing each joining node to decide its broadcast schedule based on only its one-hop neighbor information in an on-line and distributed manner. Also, once the broadcast schedule is decided, it is not changed to accommodate a newly joining node in order to prevent the consecutive changes of existing schedules. The network simulation results show that the proposed algorithm provides low latency and high reachability despite low overhead and on-line algorithm design.

In this paper, we consider a mobile, multimedia, multihop (M3) ad hoc network. Key characteristics of this system are the mobility of users, energy constraints, and the need to operate without a fixed (wired or wireless) infrastructure. In this environment, with the advent of multimedia communications, the use of the cluster architecture has been revisited to support the resource reservation and Quality-of-Service routing. We proposed an access-based clustering protocol (ABCP) that allows the network to self-organize into a cluster architecture. Three advantages are claimed by ABCP. First, by the access-based criterion, it minimizes the overhead on cluster formation so that the protocol has short execution time and good scalability. Second, ABCP unifies the algorithms for cluster initialization and maintenance, i.e., the same set of clustering functions are used by a node regardless of whether it just becomes active or is in leaving its current cluster. Third, simulation results demonstrate that the cluster structure behaves stably amid topology changes compared with techniques previously proposed. Together with the access-based criterion, a multiple access scheme is also proposed for the broadcast of control messages.

A novel combinatorial optimization algorithm called "Gradual neural network (GNN)" is presented for NP-complete broadcast scheduling problems in packet radio (PR) networks. A PR network provides data communications services to a set of geographically distributed nodes through a common radio channel. A time division multiple access (TDMA) protocol is adopted for conflict-free communications, where packets are transmitted in repetition of fixed-length time-slots called a TDMA cycle. Given a PR network, the goal of GNN is to find a TDMA cycle with the minimum delay time for each node to broadcast packets. GNN for the N-node-M-slot TDMA cycle problem consists of a neural network with N M binary neurons and a gradual expansion scheme. The neural network not only satisfies the constraints but also maximizes transmissions by two energy functions, whereas the gradual expansion scheme minimizes the cycle length by gradually expanding the size of the neural network. The performance is evaluated through extensive simulations in benchmark instances and in geometric graph instances with up to 1000 vertices, where GNN always finds better TDMA cycles than existing algorithms. The result in this paper supports the credibility of our GNN algorithm for a class of combinatorial optimization problems.