Recent developments on identifying the community structures in real-world networks have established that the community structure may be either disjoint community set (DCS) or overlapping community set (OCS), showing high resemblance with each other. Still, given a network, researchers mostly followed distinct approaches to achieve optimal solutions, either for DCS or for OCS. Moreover, prior knowledge of community structure is needed to select the appropriate class of algorithms, since one cannot produce the optimal solution for the other. In this article, a comprehensive two-phase approach based on genetic algorithm (GA) is proposed that can be applied to any small-world network to generate the DCS and the OCS very fast without any prior knowledge of the community structure. In the first phase, an upper bound on the mean path length of a community is applied, relative to the equivalent Erdős–Rényi (E–R) random graph that expedites the convergence significantly. In the second phase, the search space is reduced considerably, by selecting a smaller subset of boundary nodes of the DCS generated in the first phase, to be manipulated probabilistically. To the best of our knowledge, we are the first to consider the mean path length of the community as a key parameter for finding the good quality communities at the earliest. Experimental study on six synthetic networks and five real-world networks shows that the proposed approach not only outperforms the state-of-the-art algorithms in terms of quality and scalability, but its parallel implementation also improves the speedup significantly.

In cognitive radio systems, fast and efficient spectrum selection is a vital task to minimize the overhead of spectrum scanning, and hence to improve the response time of the system. So, the choice of channel sensing sequence plays an important role for better performance of the system. This paper proposes a co-operative Q-learning based spectrum sensing technique for the secondary users of an ad hoc network to access the primary channels. By the proposed technique, every secondary user (SU) maintains a dynamic priority list of channels based on Q-learning from its own action-observation history, as well as from spatial channel information exchange among its local neighbors. Whenever there is a demand an SU scans the spectrum according to the order in the priority list until there is a success. Simulation studies show that with significantly less computing and scanning overhead, our proposed Q-learning based approach improves the response time and call block/drop rate to offer better performance compared to other contemporary reinforcement learning based approaches.

With the advent of smarter technologies in cellular networks, often the bands used for lower versions remain unoccupied. To utilize that, in this paper, a new paradigm of cognitive radio has been proposed, where the nodes of a self-organized opportunistic ad hoc network act as the secondary users (SU) to use the white spaces of the existing cellular network. Each SU can freely move around, and in a self-organized fashion may collaborate with other neighboring SUs to gather information on the channels assigned to the cells of the primary network for cognitive use of the licensed spectrum with reduced spectrum latency. Simulation studies show that our proposed cooperative approach significantly improves the call drop/ block rate, and also results better QoS compared to the non-cooperative approach at the cost of negligible additional message overhead.

In multi-hop wireless sensor networks, the problem of uneven energy depletion is intrinsic to the system. With uniform node distribution and continuous traffic model without data fusion, no routing strategy, in general, can avoid the creation of an energy hole around the sink. However, nearly balanced energy consumption can be achieved by using non-uniform deterministic node distribution where nodes are placed in predetermined positions. In this paper, for a random non-uniform node distribution, a simple static distributed algorithm is developed for data gathering with an attempt to distribute the traffic uniformly to maximize the lifetime of the network. It requires just a one-time computation, based on the knowledge of its neighbours only during the initialisation of the network. Simulation studies show that for non-uniform random distribution of nodes the proposed algorithm with less information and less computing can enhance network lifetime significantly compared to earlier algorithms.

This paper focuses on the important issue of strategies for tracking users in a mobile communication network. Since the users are mobile, the network must keep track of where the users are, a prerequisite for routing calls to the users. We assume that the mobile users periodically inform the network of their present location. Now, it is very important to decide an efficient location updation strategy that will optimize the overhead in terms of usage of radio spectrum and power, as well as the search cost for a mobile when a call is to be set up. Static location updation strategies often result in poor performance. Three dynamic location updation strategies have been considered, namely, the time-based strategy, the movement-based strategy and the distance-based strategy. A memoryless movement pattern on a two-dimensional mesh topology of cells has been studied. Analytical models have been developed to compare the performance of the strategies. Simulation studies also have been made for performance evaluation.

The set of input-output permutations that are routable through a multistage interconnection network without any conflict (known as the admissible set), plays an important role in determining the capability of the network. Recent works on the permutation admissibility problem of shuffle-exchange networks (SEN) of size N/spl times/N, deal with (n+k) stages, where n=log/sub 2/N, and k denotes the number of extra stages. For k=0 or 1, O(Nn) algorithms exist to check if any permutation is admissible, but for k/spl ges/2, a polynomial time solution is not yet known. The more general problem of finding the minimum number (m) of shuffle-exchange stages required to realize an arbitrary permutation, 1/spl les/m/spl les/2n-1, is also an open problem. In this paper, we present an O(Nn) algorithm that checks whether a given permutation P is admissible in an m stage SEN, 1/spl les/m/spl les/n, and determines in O(Nnlogn) time the minimum number of stages m of shuffle-exchange, required to realize P. Thus, a single-stage shuffle-exchange network will be able to realize such a permutation with m passes, by recirculating all the paths m times through a single-stage, i.e., with minimum transmission delay, which, otherwise cannot be achieved with a fixed-stage SEN. Furthermore, we present a necessary condition for permutation admissibility in an m stage SEN, where n

We propose a new multistage interconnection network (MIN) called Generalized Shuffle Exchange (GSE) to connect N processors and N resources where N need not be a power of 2, but only an even number. It uses N/2 switches per stage and the number of stages is equal to [log N]. We show that GSE is a full-access network. Routing between any input-output pair in GSE is simple and can be done by using a routing vector, generated from the input and output addresses. When N is a power of 2, say 2n, GSE reduces to conventional n-stage network with unique path for each input-output pair. But, if 2n-1ngiven a specific input, there are 2[logN]-N outputs for which there exist alternative paths. Therefore, to realize any N×N permutation we are to select a set of N conflict free paths, one for each input-output connection. Now, the problem of determining whether any given permutation is realizable in a single pass by a MIN is known as the permutation admissibility problem. Here, we have presented a scheme for resolving the permutation admissibility problem in a GSE.

An NxN Benes network B(n), (n=log/sub 2/N), being a rearrangeable network, can realize any NxN permutation in a single pass. But even in the presence of a single switch fault in B(n), no NxN permutation can be implemented in one pass, it requires either recirculation through intermediate nodes, or reconfiguration of the system in a degraded mode. We characterize a class C of multiple switch faults in B(n), in the presence of which the network is always capable of realizing any arbitrary NxN permutation P in two passes. By this technique, every source-destination path is set up in a single pass, only the whole set of N source-destination paths of P is partitioned in two subsets and are realized in two successive passes. The novelty of the routing technique lies in the fact that the exact locations of the faults are not important here, only the information of an optimal region of the network containing the faulty switch is sufficient. This feature actually enables us to develop here, very fast and simple procedures for multiple switch fault detection and location as well. In this paper, we have shown that just two one bit test vectors are sufficient to detect and locate all single faults, all double faults and also many cases with 3, 4, 5 and 6 faults. Given a set F of multiple switch faults, we detect and locate its equivalent fault set F' by the fault location technique presented.

This paper explores a new hierarchy among different permutation classes, that has many applications in multistage interconnection networks. The well-known LC (linear-complement) class is shown to be merely a subset of the closure set of the BP (bit-permute) class, known as the BPCL (bit-permute-closure) class; the closure is obtained by applying certain group-transformation rules on the BP-permutations. It indicates that for every permutation P of the LC class, there exists a permutation PI in the BP class, such that the conflict graphs of P and P* are isomorphic, for n-stage MIN's. This obviates the practice of treating the LC class as a special case; the existing algorithm for optimal routing of BPC class in an n-stage MIN can take care of optimal routing of the LC class as well. Finally, the relationships of BPCL with other classes of permutations, e.g., LIE (linear-input-equivalence), BPIE (bit-permute-input-equivalence), BPOE (bit-permute-output-equivalence) are also exposed. Apart from lending better understanding and an integral view of the universe of permutations, these results are found to be useful in accelerating routability in n-stage MIN's as well as in (2n-1)-stage Benes and shuffle-exchange networks.>

A study on the isomorphism of conflict graphs in multistage interconnection networks (MINs) and its applications is outlined. A concept called group-transformation is introduced for the baseline network, which induces an equivalence partition on the set of all permutations. All members belonging to the same equivalence class have isomorphic conflict graphs. Thus, determination of conflict resolution of one permutation results in determination of conflict resolution of all other equivalent members. The BPCL (bit-permute-closure) class of permutations is defined, for which the conflict resolution problem can be settled in linear time by an earlier algorithm developed only for the BPC (bit-permute-complement) permutations. It is proved that for an N*N MIN, mod BPCL mod >or=n 2N-1, in contrast to mod BPC mod n 2n, (nlog/sup 2/ N). Conflict graphs for BPCL permutations are also characterized. An O(N) time algorithm to check membership of a given permutation to the BPCL class is described. All of these results are generalized to extend their applicability to other unique-path full-access MINs.>