论文总字数：32192字

摘 要

如今无线传感器网络已逐渐应用广泛，它是由传感器节点所组成，这些传感器节点具有微型、廉价、能量受限等一些特点，无线传感器网络是通过无线方式进行通信的多跳网络，其目的是对所覆盖区域内的信息进行采集、处理和传递。随着无线传感器的大量应用，信道自动分配问题引起人们的重视。本课题研究使用和积算法求解该问题。

本文是以无线传感器网络为背景，研究应用多代理协调的和积算法。无线传感器信道分配问题可以转换成图形着色问题。图形着色问题是NP-C问题，这类问题没有高效的、精确的快速求解方法，目前解决该类问题主要采用近似方法，例如集中式的遗传算法，本文采用分布式方法，即用和积算法来解决图形着色问题，从而开展各种应用。图形着色模型可以用来解决无线传感器网络中的分布式协调问题。本文详细阐述了无线传感器网络中一组可以交互的代理是如何最大化系统效益的。本文的工作和创新包括以下几个方面：

在带环的双向因子图中，图形因子由变量结点和函数结点组成，分别代表了代理的状态和效用函数。采用混沌序列模型对变量结点和函数结点的信息进行初始化，结点依据一组简单而高效的信息更新规则进行交互。该算法可以准确地计算所有结点的边际函数，并且经过数步更新之后，结点信息可以收敛到一个稳定值。该算法能够通过局部的、分散式的信息传递，解决全局最优化问题，该问题已经在很多不同领域有很多应用。本文的难点在于，在该无线传感器网络中，多个传感器节点之间必将存在通信干扰。而且，传感器是动态的，相互间的干扰作用也会随之发生改变。使用多代理协调技术和和积算法，可以使得传感器对于环境的改变做出及时准确的响应，并做出恰当的协调策略，确保整个网络的效率。

关键词：无线传感器网络 多代理协调 和积算法 图形着色 因子图

Research on channel assignment in wireless sensors using the Sum-Product algorithm

Abstract

Nowadays wireless sensor network has been used widely. It is composed of sensor nodes. These sensor nodes with miniature, low-cost, energy constraints and other characteristics, the wireless sensor network is to communicate through the wireless multi hop network, its purpose is covered within the region of information acquisition, processing and transmission. With the application of wireless sensor, the problem of automatic channel assignment is paid more attention. This research using the sum- product algorithm to solve the problem.

This paper is based on the wireless sensor network as the background, research and application of multi agent coordination and integrating method. The problem of the distribution of the wireless sensor can be converted into Graph coloring problem. Graph coloring problem is a NP-C problem, no efficient and accurate fast algorithm to solve these problems. Now, we mainly solve these problems by approximate methods, such as centralized genetic algorithm, this paper adopts distributed method, and using sum product algorithm to solve the problem of graph coloring, to carry out a variety of applications. In this paper, a group of interacting agents in wireless sensor networks is how to maximize the benefits of the system. The main work and contributions of this paper are as follows:

In the cyclic bipartite factor graph, graph factor consists of function nodes and variable nodes, on behalf of the state of the agent and the utility function. The information of the variable nodes and function nodes is initialized by the chaos sequence model, and the nodes are based on a group of simple and efficient information update rules. The algorithm can calculate the marginal function of all nodes accurately, and after the number of steps updated, the node information can converge to a stable value. The algorithm can propagate messages by local and distributed ways to solve the global optimization problem. This problem has been applied in many different fields. The difficulty of this paper is that there will be communication interference among the sensor nodes in the wireless sensor network. Moreover, the sensor is dynamic, and the interaction between them may change. Using multi agent coordination technology and sum-product algorithm, can make the sensor to response accurately and timely with changes of the environment, and make appropriate coordination strategy and ensure the efficiency of the whole network. 

Key Words: wireless sensor networks; the coordination of multi-agent; sum-product algorithm; factor graph; graph-color

目录

摘 要 I

Abstract II

第一章 绪论 1

1.1 课题背景 1

1.2 国内外研究现状和发展趋势 1

1.3 课题需要解决的问题和采用的研究手段 2

1.4 论文结构 4

第二章 图形着色问题 5

2.1 NP（NP-hard）难解问题 5

2.2图形着色问题概述 5

2.2.1图形着色问题的来源 5

2.2.2图形着色问题的描述 6

2.3 图形着色问题的求解方法 6

2.4图形着色问题的相关应用 7

2.5 本章小结 7

第三章 和积算法 8

3.1问题一般性描述 8

3.2 因子图 8

3.3 和积算法 9

3.3.1最大积算法 12

3.3.2循环图 12

3.3.3最大和算法 13

3.3.4最大和算法求解图形着色问题 15

3.4经验评估 18

第四章 基于混沌的最大和算法 19

4.1混沌模型 19

4.2混沌的特征 19

4.3混沌的定义 20

4.4 基于混沌的最大和算法解决图形着色问题 22

第五章 系统分析与设计 23

5.1系统总体分析 23

5.1.1需求分析概述 23

5.1.2编程语言、开发及运行环境分析 23

5.1.3界面需求分析 24

5.1.4功能需求分析 24

5.2系统设计 24

5.2.1总体设计 25

5.2.2类图的设计 26

5.2.3详细设计 26

5.2.4图形着色界面的详细设计 28

第六章 总结与展望 32

6.1总结 32

6.2进一步研究工作 33

参考文献 34

致谢 37

第一章 绪论

1.1 课题背景

无线传感器网络作为无线网络方面的一个热点问题，近十年来正在不断发展，在研究过程中，涌现出了很多优秀的理论和应用成果。关于无线传感器网络的定义如下：它是由传感器节点组成的，这些传感器节点部署在监测区域内，它们具有数量庞大、价格低廉、微型等特点，毋庸置疑，传感器是无线传感器网络的三大基本要素之一。无线传感器网络实际上是一个多跳的自组织的分布式网络系统，形成方式具体是通过无线通信方式。无线传感器网络的剩余两大基本要素为感知对象，以及观察者。无线传感器网络实质为无线网络，其目的是通过传感器节点之间的相互协作来感知相应区域中对象的信息，同时将网络覆盖区域内的对象的信息采集并处理，最终发布给信息观察者或需求者。无线传感器网络最重要的使命就是感知、采集和传递所需要的信息，因此，关于无线传感器网络的研究基本上都是围绕着这个目的而展开的。

请支付后下载全文，论文总字数：32192字