无线网络中的现有算法或协议大致可以分为两类

基于算法运行所需的信息，无线网络中的现有算法或协议大致可以分为两类：全局协议和局部协议。在全局协议中，需要一个或多个节点（通常是类似于BS的中心节点）来采集全局信息，这些信息既包括诸如整个网络拓扑结构的详细信息，也包括用于执行协议的网络最大度等与全局特性有关的简单信息。但是，在局部协议中，每个节点仅依据一些可用的局部知识来进行协议决策。为了提高精度，无线网络中的本地知识主要基于特定节点k跳范围内的邻居信息，其中k通常是一个小整数（如1或2）。一些协议（如无信标地理位置路由）不需要来自于邻居的任何信息。另一个相似实例是概率洪泛方案（Ni et al.，1999），在该方案中，每个节点使用预先定义的固定概率值，针对可能出现的重传做出自己的决策。

最短（加权）路径路由是一种典型的全局协议，它需要计算源节点和目标节点之间的最佳路由。Dijkstra和Prim这两种知名的加权路径算法都需要所有节点知晓整个网络的拓扑结构（节点之间的所有节点和边），以做出正确的决策。全局最短路径路由建立成本较高，这是由于源节点为了收集网络拓扑数据，需要交换大量的消息。在无线传感器、执行器和Ad Hoc网络中，全局信息收集成本是比较高的（除非网络是静态的、小型的或者是单跳的）。这些网络的动态特征（可能是由于节点具有移动性，或者节点的活动、到达和出发状态发生变化）需要用到局部协议，这样就可以避免由收集全局信息导致的通信开销。当网络规模比较大时，与局部算法相比，全局协议性能会急剧恶化。在无线网络中，如果可扩展性是一项重要协议要求的话，则局部协议是最佳选择。在局部协议中，决策仅依据来自于邻居的信息和固有附加信息。例如，贪婪路由（Finn，1987）是一种本地协议，它仅使用了单跳邻居和目标节点的位置信息。在贪婪路由中，路由上当前节点选择最靠近目标节点的邻居。

在许多情况下，描述协议的全局特征是以隐式特征出现的。一个实例就是用于互联网路由的知名Bellman-Ford算法，该算法也可以寻找最短路径路由。邻居节点周期性地交换其路由表，该路由表包含了针对每个目标节点的开销和转发邻居。每次信息交换结束后，路由表即进行更新。由于邻居之间的信息交换仅是以显式通信方式进行的，因而该算法虽然看似一种局部算法，实则是远程节点以摘要形式发送重要消息操作的重复应用。因此，该算法是一种全局算法。在研究文献中，虽然每个节点的消息复杂性是不受限制的（通常为O（d），其中d为邻居数），但是其他一些算法仍然宣称是局部算法。尽管所需信息看起来又具备严格的局部特征，可是采集信息在过程中可能仍然具备全局特征，因而该算法不是局部算法。(www.xing528.com)

在建立和维护阶段，局部协议可以进一步划分为基于所需信息量和基于开销的协议。所需信息量与消息复杂性有关，消息复杂性定义为协议中每个节点交换的消息平均数。在网络建立阶段，一些局部协议可能需要在邻居之间交换大量的消息。消息数比得上采集和使用的全局信息数。在维护阶段，当部分网络发生变化时，一些局部协议（在建立阶段）需要进行消息传播和整个网络的重新计算，如最小生成树（Minimal Spanning Tree，MST）和典型的簇状结构的维护。因此，局部协议可以进一步划分为本地局部协议（维护阶段的消息复杂性比较低）和准本地局部协议（局部变化可能触发全局更新）。节点的移动性和激活与休眠模式之间的状态变化需要用到局部协议，最好是本地局部协议。

需要注意的，在可扩展传感器与执行器网络中，对全局算法的批判并不意味着这些算法无益于协议设计。例如，当局部（如两跳）知识非常有限，导致某些情况下存在多种可用协议时，全局算法就变得非常有用。这一点将在本书后面章节进行阐述。