Methods and apparatus for using end nodes, e.g., wireless terminals, to discover base stations and communicate information about discovered access nodes, e.g., base stations, to other access nodes in a system are described. As the wireless terminal roams in the system and new access nodes are encountered, one or more physically adjacent access nodes will be informed of the presence of the new access node as a result of communications with the wireless terminal. A message indicating an access node's inability to route a message to another access node which is known to a wireless terminal may trigger the wireless terminal to begin the process of updating access node routing and neighbor information.