无线自组网是由多个无线移动节点临时组成的不依赖任何基础通信设施的无线多跳对等网,网络中的每一个节点同时具有普通网络节点和路由器的双重功能。而服务发现协议是网络节点自动从网络中搜索所需服务的技术。服务发现协议的最终目标就是要实现无人管理的网络,将人从乏味繁重的网络维护工作中解脱出来。所以,简单高效、健壮灵活、具有良好扩展性的服务发现协议是无线自组网实用化的一项关键技术。研究无线自组网基本性质的准确的闭合的解析描述对包括服务发现协议在内的无线自组网协议设计工作具有重要意义,如用于指导协议参数的设置、针对性地优越协议操作、估算协议的性能等。因此本文第二章基于组合学方法和极限思想研究了矩形区域内节点均匀分布的无线自组网的几项基本属性,网络中链路总数的期望值,网络中节点度数分布情况,以及网络连通性与无线信号传输半径的关系等,得出了其解析描述。GSD (Group-based Service Discovery prototcol)协议是个典型无线自组网服务发现协议。它采用了基于组的服务需求包智能转发技术,该技术根据所需服务的特点和本地搜集整理的信息将服务需求包有选择地发送给部分节点,避免了泛洪式转发策略。但GSD在具体操作中存在明显问题:对每个选中节点都要单播发送一个服务需求包,显著增大了服务需求包开销。虽GSD存在明显的问题,但其基于组的服务需求包智能转发技术是非常值得借鉴的,为此本文提出了转发节点集中技术和单播通信广播模拟技术以弥补GSD的问题。转发节点集中技术用所谓的转发节点代替候选节点作为服务需求包的转发目标,而单播通信广播模拟技术把多个以单播方式发送给不同接收节点的信息包用一个以广播方式发送的信息包来代替。数学分析和仿真研究都证明新技术能显著节省服务需求包开销。仿真研究证明采用着两项新技术的FaBGSD协议具有更小的服务需求包开销,更高的效率,更快的响应速度。但FaBGSD协议仍存在无效候选节点及转发节点选取策略效率低等方面的不足。为弥补其不足,本文提出了隐含服务节点剪除技术和隐含服务节点覆盖集合最小化技术。隐含服务节点剪除技术尽量精简要覆盖的隐含服务节点数量,而隐含服务节点覆盖集合最小化技术则用最小的转发节点集合来覆盖隐含服务节点。本文将隐含服务节点覆盖集合最小化技术的核心技术概括成隐含服务节点覆盖集合问题,证明了该问题的NP完全性,给出了基于贪婪思想的启发式算法,得出了算法的近似系数。仿真研究证明了采用了这