مسیریابی خوشه بندی بر اساس برنامه ریزی عدد صحیح مختلط برای شبکه های حسگر بی سیم ناهمگن Clustering routing based on mixed integer programming for heterogeneous wireless sensor networks

1 Introduction A wireless sensor network, which consists of differently typical and functional sensor nodes, is called heterogeneous wireless sensor network. A rational use of heterogeneous nodes can improve applying ability and prolong the lifetime in wireless sensor network. The heterogeneous wireless sensor network is widely applied to military, medical, environmental, industrial and commercial, family life and so on. In heterogeneous wireless sensor network, the heterogeneous node can complete complex communication tasks, because it has sustainable energy resource and doesn’t require frequent replacement. Furthermore, the communications and data processing capacity of heterogeneous nodes are far higher than those of the common nodes. But heterogeneous nodes are expensive, it is necessary to consider how to balance the energy consumption and prolong network lifetime by deploying minimum number of heterogeneous nodes. In this paper, a clustering routing algorithm for heterogeneous wireless sensor network (CHRA) is presented to balance energy and prolong the network lifetime. The main contributions of this paper are shown as follows: • The model of optimal placement of heterogeneous nodes is built. The problem of minimizing function of total effective transmission distance is converted into the optimal problem of heterogeneous nodes position selection by mix integer programming. A decomposition method, which consists of Lagrange relaxation and Benders decomposition, is used to solve the problem of mix integer programming. • The model of optimal number of heterogeneous nodes and cluster heads is built respectively. The method to obtain optimal solution of number of heterogeneous nodes and number of cluster heads is presented respectively. • A clustering routing algorithm for heterogeneous wireless sensor network (CHRA) is presented, which consists of the heterogeneous routing algorithm for wireless sensor network and a cluster heads selecting algorithm by LEACH-C. • We evaluate the performance of our proposed CHRA routing and some previous typical routings via extensive experiments. The results indicate that our proposed routing algorithm can availably prolong network lifetime and stable period. And it can also balance the energy consumption significantly. The remainder of the paper is organized as follows. Section 2 introduces related work. Section 3 proposes the optimal placement method of heterogeneous nodes. Section 4 discusses the performance of CHRA is better than that of the heterogeneous routing algorithm (HRA), which is presented in Section 3.1.1, and describes the details of the implementation of our proposed algorithms. Section 5 provides comparison and analysis of experiment results.