The middleware is the most commonly used solution to address the location privacy. But it becomes a bottleneck in terms of system performance and availability as the entire client's service transactions are routed through the middleware to the actual Location Based Service Providers (LSP). The proposed architecture mainly targets a variety of applications where the availability of the services is probably more important than the location security. In the new flexible middleware based architecture the client and the LSPs can communicate directly. Autonomy on the client-server communication increases the possibility of communication even in the scenarios where the middleware is not available. But it also introduces authentication and security challenges to be addressed. The trusted middleware is used to generate the authentication certificates containing the Proxy Identity (also called Pseudonyms) to fulfill the authentication requirements at the LSP servers. The rest of transactions among the clients and the LSPs are accomplished independently. Further, the level of anonymity can be tuned by altering pseudonyms generation techniques i.e. "One-to-One", "One-to-Many" and "Many-to-One" depending on the type of the service and security requirements. It also attempts to maintain almost the same level of security for the targeted services. © 2012 ICST Institute for Computer Science, Social Informatics and Telecommunications Engineering.